我们都知道 DFS（深度优先搜索）和 BFS（广度优先搜索）。它们各有不同的适应场景。

BFS 可以看成是层序遍历。从某个结点出发，BFS 首先遍历到距离为 1 的结点，然后是距离为 2、3、4…… 的结点。
因此，BFS 可以用来求最短路径问题。BFS 先搜索到的结点，一定是距离最近的结点。

（最短路径的） BFS 代码

我们都知道 BFS 需要使用队列，代码框架是这样子的（伪代码）：

  1. while queue 非空:
  2.     node = queue.pop()
  3.     for node 的所有相邻结点 m:
  4.         if m 未访问过:
  5.             queue.push(m)

但是用 BFS 来求最短路径的话，这个队列中第 1 层和第 2 层的结点会紧挨在一起，无法区分。因此，我们需要稍微修改一下代码，在每一层遍历开始前，记录队列中的结点数量 nn ，然后一口气处理完这一层的 nn 个结点。代码框架是这样的：

  1. depth = 0 # 记录遍历到第几层
  2. while queue 非空:
  3.     depth++
  4.     n = queue 中的元素个数
  5.     循环 n 次:
  6.         node = queue.pop()
  7.         for node 的所有相邻结点 m:
  8.             if m 未访问过:
  9.                 queue.push(m)