图的深度与广度优先遍历

深度优先遍历算法口诀

• 访问根节点
• 对根节点的没访问过相邻节点挨个进行深度优先遍历
  code

const graph = {
  0: [1, 2],
  1: [2],
  2: [0, 3],
  3: [3],
};
const dfs = (n) => {
  console.log(n); //访问根节点
  visted.add(n); //访问过的做一个记录
  graph[n].forEach((item) => {
    if (!visted.has(item)) {
      dfs(item); //递归调用
    }
  });
};
dfs(2);
//结果为   2  0  1  3

广度优先遍历算法口诀

• 新建一个队列，把根节点入队
• 把队头出队并访问
• 把队头的没访问过的相邻节点入队
• 重复第二三步，直到队列为空
  code

const visited = new Set();
const q = [2]; //根节点入队
visited.add(2); //添加到访问记录
while (q.length) {
  //循环
  const n = q.shift(); //队头出队并访问
  console.log(n);
  graph[n].forEach((item) => {
    //把队头没访问过的相邻节点入队
    if (!visited.has(item)) {
      q.push(item);
      visited.add(item);
    }
  });
}

执行结果

总结

• 图是网络结构的抽象模型，是一组由边连接的节点
• 图可以表示任何二次元关系，比如道路，航班
• JS 中没有图，但是可以用，Object 和 Array 构件图
• 图的表示法：邻接矩阵,邻接表
• 图的常用操作: 深度/广度优先遍历