广度优先搜索

队列保存的是尚未展开的波前。第 $k$ 层全部排在第 $k+1$ 层之前，所以一次“首次发现”同时完成两件事：确认可达，并锁定最少边数。父指针只是从可能的多条最短路中选择一条；距离不随邻接次序改变，具体搜索树却会改变。

这一点也刻画了 BFS 与深度优先搜索公理库深度优先搜索Depth-first search · DFS沿未访问边尽可能深入后回溯的图遍历算法。的分工。DFS 的栈优先完成当前分支，适合暴露祖先与退出顺序；BFS 的 FIFO 次序保留距离层。把队列机械换成栈，仍能遍历可达集合，却失去“首次发现即最短”的结论。

设无向图的边为

按邻接点字母顺序扫描，队列初始为 $[s]$；展开 $s$ 后变为 $[a,b]$，两点距离都设为1。取出 $a$，发现 $c$ 并得到队列 $[b,c]$；再取出 $b$ 时，$c$ 已在队中，不能重复加入。接着 $c$ 发现 $d$，最终队列清空。

从 $s$ 出发的各层依次是 $\{s\}$、$\{a,b\}$、$\{c\}$、$\{d\}$，所以 $d[c]=2$、$d[d]=3$。若 $a$ 先于 $b$ 出队，可能记录 $\pi [c]=a$；反过来则可能记录 $\pi [c]=b$。两棵 BFS 树不同，但 $c,d$ 的距离相同。另一个孤立顶点 $x$ 从未入队，保持 $d[x]=+\mathrm{\infty }$。若要遍历整张非连通图，可从每个尚未发现的顶点重新启动，得到 BFS 森林；此时不同树根之间没有由本次搜索定义的有限距离。

边权破坏按边数分层。若 $s\to a$ 的权为 $10$，而 $s\to b$、$b\to a$ 的权均为 $1$，BFS 会偏好一条边的直达路，权重最短路却是成本 $2$ 的绕行。一般非负权应使用Dijkstra 算法公理库Dijkstra 算法Dijkstra's algorithm在非负边权图中逐次确定最短距离的单源最短路算法。；权只取 $0$ 与 $1$ 时，0–1 BFS 用双端队列公理库双端队列Deque · Double-ended queue在同一有序序列的首尾两端都支持插入与删除的抽象数据类型。把零权改进放在队首、一权改进放在队尾。

发现标记必须在入队时写入。在上例中，若 $a$ 把 $c$ 入队却未标记，随后展开 $b$ 时会再次放入 $c$。这样“每个顶点至多一次入队”的空间与工作量论证就失效了；若重复出队时还继续展开邻接表，额外工作会进一步传播。平行边不改变最少边数，但应共享同一个“已发现”状态；自环也不能触发重新入队。

BFS 是单位权最短路公理库最短路问题Shortest-path problem在有限有向实权图中寻找源点到各顶点的最小有向游走成本。的标准算法，也能按距离奇偶给二分图公理库二分图Bipartite graph顶点可分成两个独立侧、且每条边都跨越两侧的有限简单无向图。二染色、枚举连通分量公理库连通分支Connected component包含给定点的极大连通子集。。Edmonds–Karp 用它选择残量边数最少的增广路，Dinic 算法公理库Dinic 算法Dinic's algorithm分层残量网络上反复计算阻塞流的最大流算法。则用 BFS 构造残量层次图；后两者的“距离”是当前残量网络中的弧数，会随增广而变化。

当图的顶点各自运行程序、只能沿边通信时，同步分布式图模型与 BFS 波前公理库同步分布式图模型与 BFS 波前Distributed graph models · LOCAL · CONGEST · 分布式 BFS从节点局部输入出发构造指定根的 BFS 树，证明逐轮距离、通信开销与全局最小标识的局部性下界。用同步轮次组织距离层，让每个节点输出自己的距离和父端口。这里分析的是通信轮数与消息条数：输出在根的离心率轮后稳定，一次转发至多发送 $2m$ 个数据包；这些指标与本页 FIFO 实现的 RAM 总工作量回答不同问题。

在有限状态系统中，显式状态模型检查公理库显式状态模型检查Explicit-state model checking · Explicit model checking逐个生成和存储可达状态，以图搜索检查安全性及接受环的模型检查路线。可用 BFS 按反例长度枚举可达配置；一旦命中坏状态，父指针给出一条最短转移数的反例轨迹。这里“最短”只相对于所选状态编码与一步转移，BFS 是搜索算法，状态语义与要检查的性质仍须另行定义。

若图由状态转移规则隐式给出，$n,m$ 应理解为实际生成并访问的状态与转移数；邻居生成、哈希去重和状态编码可能主导成本。外存模型还按块传输计费，不能把 RAM 中的逐边扫描数直接当作 I/O 次数。一般的割或谱稀疏化也不保证逐对无权距离不变，除非所用稀疏器明确承诺保距。