形式陈述

对图 $G=(V,E)$$G=(V,E)$ 和源点 $s$$s$，广度优先搜索维护先进先出队列。初始化 $d(s)=0$$d(s)=0$ 并将 $s$$s$ 入队；每次取出 $u$$u$，扫描其邻接点 $v$$v$，若 $v$$v$ 尚未发现，则设置

$$ d(v)=d(u)+1, $$$$d(v)=d(u)+1,$$

记录父节点 $\pi(v)=u$$\pi (v)=u$ 并入队。

在无权图中，BFS 结束后，对每个从 $s$$s$ 可达的 $v$$v$，$d(v)$$d(v)$ 等于最短路边数 $\delta(s,v)$$\delta (s,v)$。邻接表实现的时间复杂度为 $O(|V|+|E|)$$O(|V|+|E|)$，空间为 $O(|V|)$$O(|V|)$。

直觉

队列使搜索按离源点的层次向外扩张：距离 $k$$k$ 的所有顶点在距离 $k+1$$k+1$ 的顶点之前被发现，所以第一次到达就是最短边数。

例子与边界

在无向图中，BFS 树路径给出源到每个可达顶点的最短无权路。若边有不同权重，普通 BFS 不再正确；边权全为 $1$$1$ 或同一正常数时才适用，非负一般权重需 Dijkstra，$0/1$$0/1$ 权重可用双端队列变体。

推论与应用

BFS 用于无权最短路、连通分量、二分图检测和最少步状态搜索。复杂度 $O(V+E)$$O(V+E)$ 假设邻接表；若使用邻接矩阵，扫描所有潜在边通常为 $O(V^2)$$O(V^2)$。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Ch. 20。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，§3.2。