广度优先搜索
广度优先搜索（BFS）按与起点的距离逐层访问节点。它用先进先出的队列管理已发现、尚待处理的节点。在无权图中，首次到达一个节点就得到经过边数最少的路径，时间复杂度为 O(V + E)。
水面的波纹先到达近处，再到达远处。BFS 的队列维持同样的层次：新节点从队尾加入，下一个处理的节点从队首取出，后发现的下一层不能越过前面等待的节点。
广度优先搜索如何工作
先把起点入队，标记为已访问，距离设为 0。只要队列非空，就取出队首节点，检查它的邻居。对尚未发现的邻居，记录距离为当前节点距离加 1，标记后加入队尾。
标记应在入队时完成。 若只把标记推迟到出队，又没有另设防重机制，同一节点可能被几个邻居重复加入，距离也可能被后来的路径覆盖。图模式代码把 visited.add(nb) 与入队放在同一个 if nb not in visited 分支里。
本课有两种模式。Tree 模式中，每个节点只有一条从根到达的路径，不会重复汇合，代码省略已访问集合。Graph 模式允许路径汇合和环，需要该集合防止重复发现。指向已发现节点的边检查后跳过，不再入队：目标是当前节点在 BFS 树中的祖先时，动画标作 back edge，否则标作 cross edge。
队列按距离不减的顺序出队。首次发现节点时，先前处理的路径不会比之后的路径更长，所以该距离已经是无权图中的最短距离。
广度优先搜索逐步演示
默认设置为 Graph 模式、Simple 预设、起点 0。图有七个节点：0 → [1, 2]、1 → [3, 4]、2 → [5]、4 → [5]、5 → [6]，3 和 6 没有后继。节点 5 可以经由 2 或 4 到达。
- 0 入队：标记，距离
d = 0，队列为[0]。 - 0 出队：发现 1、2，距离都为
d = 1，队列为[1, 2]。 - 1 出队：发现 3、4，距离都为
d = 2，队列为[2, 3, 4]。 - 2 出队：首次发现 5，记录父节点为 2，
d(5) = 2，队列为[3, 4, 5]。 - 3 出队：没有新节点，队列为
[4, 5]。 - 4 出队：检查
4 → 5时，5 已经被发现。这条路径需要三条边，不比已有的两条边更短，所以跳过，不入队，队列为[5]。 - 5 出队：发现 6，距离
d = 3，队列为[6]。随后 6 出队，没有新节点，队列变空。
访问顺序为 0、1、2、3、4、5、6，分层距离为 0 / 1、1 / 2、2、2 / 3。关键是第六步：已访问集合让第二次到达 5 成为一次跳过，而不是重复工作。
切到 Tree 模式的 Balanced 预设，完整二叉树的层序也是 0, 1, 2, 3, 4, 5, 6，没有汇合边。对同一棵树，DFS 的先序顺序则是 0, 1, 3, 4, 2, 5, 6。图模式的 Cyclic 预设展示环：闭合环的边指向已发现节点，因此被跳过。
动画底部显示队列：元素从队尾进入、队首离开。节点在未到达时为浅蓝色，已发现且等待处理时为橙色，扫描完成后为绿色。d= 标签显示距离，被跳过的边（back 或 cross）会闪红。
时间与空间复杂度
| 情况 | 时间复杂度 | 额外空间 |
|---|---|---|
| 一次遍历 | O(V + E) | O(V) |
每个可达节点只入队、出队一次，每个访问到的邻接表项只检查一次。队列和已访问集合最多容纳 O(V) 个节点。
宽层会使队列变大；队列在处理一层时，也可能同时保存本层剩余节点和下一层已发现节点。长链通常只需很短的队列。DFS 的空间压力则常来自深路径，两者最坏额外空间都是 O(V)。
边界情况
- 单节点、无边：起点入队、出队，没有邻居，结束。
- 不连通图：只访问起点可达的节点；在无向图中就是起点所在的连通分量。遍历全图需要从尚未访问的节点重新启动。
- 有环：已发现标记阻止节点重复入队，环不会让队列无限增长。
- 宽图与深图：宽的搜索边界需要较大队列，长链的队列通常很短。
常见错误
- 到出队时才标记，却没有防重处理：同一节点可能被多个邻居重复加入。当前实现应在入队时标记。
- 用普通 BFS 求不同权重边的最短路：BFS 最小化边数，只有边成本相同时才能据此最小化总成本。非负权重图可用 Dijkstra 算法。
- 把队列换成栈：先进先出变成后进先出，访问顺序会深入路径，而不再逐层扩展。检查语言库里
pop取的是哪一端。 - 在图模式删除已访问集合：环会反复把同一节点加入队列。只有路径不会汇合或成环的树结构，才可省去这类防重状态。