图的遍历分为两种，深度优先遍历（depth-first）和广度优先遍历（breadth-first）

深度优先遍历 dfs

  1. // 嵌套多一层是为了定义 marker 默认值，实际的遍历算法是内部的 a
  2. function dfs(v) {
  3.   let marker = []
  4.   for (let i in this.vertexes) {
  5.     marker[this.vertexes[i]] = false
  6.   }
  7.   let _this = this
  8.   let a = function (v) {
  9.     console.log(v)
  10.     marker[v] = true
  11.     for (let j in _this.adj[v]) {
  12.       let item = _this.adj[v][j]
  13.       if (!marker[item]) {
  14.         a(item)
  15.       }
  16.     }
  17.   }
  18.   a(v)
  19. }

广度优先遍历 bfs

  1. bfs(v) {
  2.   let marker = []
  3.   for (let i in this.vertexes) {
  4.     marker[this.vertexes[i]] = false
  5.   }
  6.   let _this = this
  7.   let a = function (v) {
  8.     marker[v] = true
  9.     let queue = []
  10.     queue.push(v)
  11.     while (queue.length > 0) {
  12.       let item = queue.shift()
  13.             console.log(item)
  14.       if (!_this.adj[item]) {
  15.         continue
  16.       }
  18.       _this.adj[item].forEach(i => {
  19.         if (!marker[i]) {
  20.           queue.push(i)
  21.           marker[i] = true
  22.         }
  23.       })
  24.     }
  25.   }
  26.   a(v)
  27. }