BFS可视化工具在线

伪代码

整个算法就是一个队列加一个已访问集合。BFS 之所以出名的其他性质，全都源自队列交还结点的顺序。

BFS(图, 源点):
    已访问 = {源点}
    dist[源点] = 0
    队列 = [源点]

    当队列非空时:
        u = 队列.取出队首()
        对 u 的每个邻居 v:
            若 v 不在已访问中:
                已访问.加入(v)
                dist[v] = dist[u] + 1
                父结点[v] = u
                队列.加入队尾(v)

不变式是：队列中始终只包含至多两个相邻距离层的结点，且按距离非递减排列。正是这一条性质保证了 dist 的正确性：结点在第一次被看到时就确定了距离，此后不可能以更小的代价被抵达。

分步示例演算

从 A 出发在可视化工具默认加载的图上运行 BFS，可以在上方面板中逐步对照。

示例图: 无向边 A-B (2)、A-C (3)、B-C (1) 和 C-D (4)。BFS 完全忽略权重，只数跳数，因此每条边都算作一。

1. 开始. 把 A 标记为已访问，dist 为 0，放入队列。队列：[A]。
2. 取出 A. A 的邻居是 B 和 C，都未访问。两者都得到 dist 1 和父结点 A。队列：[B, C]。
3. 取出 B. B 的邻居是 A 和 C。两者都已访问：A 是源点，C 刚才已被 A 认领。不添加任何结点。这一步说明了 BFS 为何从不重复访问：经由 B 抵达 C 需要 2 跳，而已记录的是 1 跳。队列：[C]。
4. 取出 C. C 的邻居是 A、B 和 D。只有 D 是新的，因此它得到 dist 2 和父结点 C。队列：[D]。
5. 取出 D. D 唯一的邻居 C 已访问。队列清空，搜索结束。

最终距离为 A 0、B 1、C 1、D 2，父指针给出最短路径树 A 到 B、A 到 C、C 到 D。注意 BFS 经由 C 抵达 D，尽管该路径的加权代价为 7，而 A 到 B 到 C 只需 3：它唯一优化的是跳数，这正是加权图必须改用 Dijkstra 的原因。

复杂度及其来源

时间: O(V + E) · 空间: O(V)

每个结点至多入队一次，因为它在入队时而非出队时就被标记为已访问，这把外层循环限制在 V 次迭代内。循环体内的工作量与当前结点的度成正比，而无向图中所有度之和为 2E，因此扫描邻居总共为 O(E)。空间主要由已访问集合、距离数组和队列决定，各为 O(V)。若改用邻接矩阵，每个结点的邻居扫描变为 O(V)，整体退化为 O(V 的平方)。

何时使用广度优先搜索，何时不宜

只要边没有权重，BFS 就是默认选择。一旦出现权重，或目标从距离转向结构，就该换别的算法。

常见陷阱

• 在出队时而非入队时标记已访问. 若结点只在离开队列时才标记，它在首次出队前可能被反复入队。在稠密图上这会把线性遍历变成平方级，并可能耗尽内存。请在压入队列的那一刻就标记。
• 在加权图上使用 BFS. BFS 数的是跳数而非权重。若 A 到 C 是一条代价 100 的边，而 A 到 B 到 C 是两条边共计 2，BFS 会报告代价 100 的路径更短。此时应改用 Dijkstra。
• 仅凭距离重建路径. 距离只说明有多远，不说明走哪条路。在赋值距离时同时保存父指针，然后从终点沿父指针回溯并反转结果。
• 用递归代替队列. 递归遍历本质上就是深度优先，无论叫什么名字。BFS 需要显式的先进先出队列，它没有自然的递归写法。

常见问题

广度优先搜索有什么用？

BFS 在无权图中求最短路径，检测连通性与二分性，并按层遍历树。它也是 Edmonds-Karp 最大流算法内部寻找增广路径的手段，并支撑社交网络与路由网络中的最少跳数查询。

BFS 的时间复杂度是多少？

使用邻接表时为 O(V + E) 时间和 O(V) 空间，其中 V 是结点数，E 是边数。使用邻接矩阵时变为 O(V 的平方)，因为每次邻居扫描都要花 O(V)，与实际的度无关。

BFS 总能找到最短路径吗？

在无权图中是，在加权图中不是。BFS 按跳数非递减的顺序扩展结点，所以第一次抵达某结点时用的边数必然最少。一旦边带有不同权重，这条保证就失效了，因为边数最少与总权重最小不再是同一件事。

BFS 和 DFS 有什么区别？

BFS 用队列逐层探索，在无权图中求最短路径。DFS 用栈或递归沿一条分支走到底，揭示环、拓扑序、强连通分量等结构信息。在宽图上 BFS 更耗内存，在深图上 DFS 更耗内存。

BFS 能检测环吗？

能。在无向图中，若 BFS 抵达一个已访问且不是当前结点父结点的结点，该边就闭合了一个环。在有向图中 BFS 并不合适，通常改用 Kahn 拓扑排序或带边分类的 DFS。