介绍下深度优先遍历和广度优先遍历，如何实现？

//定义类
class Graph {
  constructor() {
    this.vertices = new Set();
    this.edges = new Map();
  }
  addVertex(v) {
    if (this.vertices.has(v)) return;
    this.vertices.add(v);
    this.edges.set(v, new Set());
  }
  addEdge(v1, v2) {
    if (!this.vertices.has(v1)) return;
    if (!this.vertices.has(v2)) return;
    const v1s = this.edges.get(v1);
    const v2s = this.edges.get(v2);
    v1s.add(v2);
    v2s.add(v1);
  }
  toString() {
    let s = "";
    for (let v of this.vertices) {
      s += `${v}->[${[...this.edges.get(v)].join()}]\n`;
    }
    return s;
  }

  /*
  深度优先遍历（DFS）
  深度优先遍历（Depth-First-Search），是搜索算法的一种，它沿着树的深度遍历树的节点，尽可能深地搜索树的分支。当节点v的所有边都已被探寻过，将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已探寻源节点到其他所有节点为止，如果还有未被发现的节点，则选择其中一个未被发现的节点为源节点并重复以上操作，直到所有节点都被探寻完成。
  简单的说，DFS就是从图中的一个节点开始追溯，直到最后一个节点，然后回溯，继续追溯下一条路径，直到到达所有的节点，如此往复，直到没有路径为止。
  DFS 可以产生相应图的拓扑排序表，利用拓扑排序表可以解决很多问题，例如最大路径问题。一般用堆数据结构来辅助实现DFS算法。
  注意：深度DFS属于盲目搜索，无法保证搜索到的路径为最短路径，也不是在搜索特定的路径，而是通过搜索来查看图中有哪些路径可以选择。
  */
  dfs() {
    const marked = {};
    const dfsVisit = (v) => {
      console.log(v);
      marked[v] = true;
      const edge = this.edges.get(v);
      for (let nv of edge) {
        if (!marked[nv]) dfsVisit(nv);
      }
    };
    for (let v of this.vertices) {
      if (!marked[v]) dfsVisit(v);
    }
  }

  /*
  广度优先遍历（BFS）
  广度优先遍历（Breadth-First-Search）是从根节点开始，沿着图的宽度遍历节点，如果所有节点均被访问过，则算法终止，BFS 同样属于盲目搜索，一般用队列数据结构来辅助实现BFS
  BFS从一个节点开始，尝试访问尽可能靠近它的目标节点。本质上这种遍历在图上是逐层移动的，首先检查最靠近第一个节点的层，再逐渐向下移动到离起始节点最远的层
  */
  bfs(root) {
    const marked = {};
    const queue = [];

    marked[root] = true;
    queue.push(root);

    while (queue.length) {
      const c = queue.shift();
      console.log(c);

      const edge = this.edges.get(c);
      for (let nv of edge) {
        if (!marked[nv]) {
          marked[nv] = true;
          queue.push(nv);
        }
      }
    }
  }
}

//测试
var graph = new Graph();
var vertices = [1, 2, 3, 4, 5];
for (var i = 0; i < vertices.length; i++) {
  graph.addVertex(vertices[i]);
}
graph.addEdge(1, 4); //增加边
graph.addEdge(1, 3);
graph.addEdge(2, 3);
graph.addEdge(2, 5);

console.log(graph.toString());

/*
1->[4,3]
2->[3,5]
3->[1,2]
4->[1]
5->[2]
*/

console.log("dfs:");
graph.dfs();
/*
dfs:
1
4
3
2
5
*/

console.log("bfs:");
graph.bfs(1);

/*
bfs:
1
4
3
2
5
*/

//测试2
var graph2 = new Graph();
var vertices = [1, 2, 3, 4, 5, 6, 7, 8];
for (var i = 0; i < vertices.length; i++) {
  graph2.addVertex(vertices[i]);
}
graph2.addEdge(1, 2); //增加边
graph2.addEdge(2, 4);
graph2.addEdge(2, 5);
graph2.addEdge(4, 8);
graph2.addEdge(5, 8);
graph2.addEdge(1, 3);
graph2.addEdge(3, 6);
graph2.addEdge(3, 7);
graph2.addEdge(6, 7);

console.log(graph2.toString());

/*
1->[2,3]
2->[1,4,5]
3->[1,6,7]
4->[2,8]
5->[2,8]
6->[3,7]
7->[3,6]
8->[4,5]
*/

console.log("dfs:");
graph2.dfs();
/*
dfs:
1
2
4
8
5
3
6
7
*/

console.log("bfs:");
graph2.bfs(1);
/*
bfs:
1
2
3
4
5
6
7
8
*/