广度优先搜索
复习
- 字典树（进阶）：字典树按字符逐层组织字符串
- 图：由节点和边组成
- 图的表示：邻接矩阵与邻接表
TL;DR
- 广度优先搜索一层一层向外扩张
- 它用队列维护待访问的节点
- 在无权图中，它第一次到达某点就是最短路径
- 访问过的节点要标记，避免绕圈
正文
存好图之后，第一个问题是：怎样系统地把它走一遍？ 有两种经典走法，先看广度优先搜索（BFS，Breadth-First Search）。
一层一层往外扩
BFS 的策略像水波扩散：从起点开始，先访问它的所有直接邻居，再访问邻居的邻居，一层一层往外推。
要按这个顺序走，靠的正是队列：起点入队；每次从队首取出一个节点访问，把它的、还没访问过的邻居都加入队尾。因为队列是先进先出，先入队的（更靠近起点）先被处理，天然形成“一层一层”的顺序。
同时，要用一个标记记录“哪些节点已经访问过”。否则遇到环，就可能反复绕圈、永远走不完。
为什么它能找到最短路径
BFS 有一个非常重要的性质：在无权图里，它第一次到达某个节点时，走的就是边数最少的路径。
道理很直觉：BFS 是一圈一圈扩散的，先访问的一定是离起点近的。当你第一次碰到目标时，前面那些更近的层都已经处理过了，所以不可能有更短的走法还没被发现。第一次到达，就是最短。
注意，这个结论只对无权图（或者说每条边代价相同）成立。如果边有权重，就得用后面的 Dijkstra 等算法了。
它能做什么
因为“按层”“最短”这两个性质，BFS 常被用来：
- 求无权图的最短路径
- 计算“几度人脉”这样的关系距离
- 网络爬虫按层抓取
只要问题问的是“最少几步能到”，BFS 往往就是答案。
那么，如果不在意“最短”，只想尽快探遍所有能到的角落呢？那就轮到深度优先搜索了。
思考题 1
BFS 为什么用队列，而不是栈？
思考题 2
为什么在无权图里，BFS 第一次到达某节点就是最短路径？
小结
知识点
- BFS 一层层向外扩张，用队列维护待访问节点
- 需标记已访问节点，避免绕圈
- 无权图中第一次到达即最短路径
- 常用于无权最短路、人脉距离、爬虫
参考资料
- Wikipedia(zh)：广度优先搜索：按层扩展的图遍历算法
- Wikipedia(zh)：队列：BFS 依赖的先进先出结构
思考题答案（仅供参考）
思考题 1
因为 BFS 要“先访问离起点近的”，而队列是先进先出，先入队的节点会先被处理，保证按层次推进。若用栈（后进先出），就会变成一条路走到底，那是 DFS 的行为。
思考题 2
因为 BFS 按层扩散，先访问的一定离起点更近。第一次到达某个节点时，所有更近的层都已经被处理完，不可能还存在一条更短、却还没被发现的路径，所以此时的距离就是最短的。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪