BFS——广度优先搜索算法详解

广度优先搜索（BFS）是一种图算法，它会按照节点到起始节点的距离顺序访问各个节点。它会先检查所有与起始节点相差一条边的节点，再访问相差两条边的节点，然后是三条边，依此类推。

这种逐层推进的顺序就是它的核心思想。如果图是无权图，或者每条边的代价都相同，那么 BFS 还可以求出从起始节点到每个可达节点的最短路径长度。

广度优先搜索的作用

BFS 使用一种队列，也就是先进先出（FIFO）的列表。队列正是保证分层顺序的关键：越早被发现的节点，越早被处理。

常见流程是：

如果你还记录了每个节点的父节点，那么在搜索结束后，就可以还原出一条最短路径。

假设节点 $A$ 是起点。它的直接邻居到 $A$ 的距离是 $1$ ，所以它们会最先进入队列。只有在这些节点被处理之后，它们那些尚未访问的邻居才会进入队列，这就意味着下一波节点的距离是 $2$ 。

这就是为什么 BFS 会自然地按与起点的距离对节点分组。它并不是在估计哪条路径更短，而是队列会强制搜索先完成所有边数更少的路径，再去考虑更长的路径。

使用下面这张图：

A \to \{B, C\}, \qquad B \to \{D\}, \qquad C \to \{E\}, \qquad D \to \{F\}, \qquad E \to \{F\}

从 $A$ 开始。队列会这样变化：

[A] \to [B, C] \to [C, D] \to [D, E] \to [E, F] \to [F]

这表示：

首先处理 $A$ ，然后加入 $B$ 和 $C$ 。接着处理 $B$ ，再处理 $C$ ，于是加入 $D$ 和 $E$ 。之后处理 $D$ 和 $E$ ，最终到达 $F$ 。

因此，BFS 的访问顺序是：

A,\ B,\ C,\ D,\ E,\ F

从 $A$ 出发的距离分别是：

\operatorname{dist}(A)=0,\quad \operatorname{dist}(B)=1,\quad \operatorname{dist}(C)=1,\quad \operatorname{dist}(D)=2,\quad \operatorname{dist}(E)=2,\quad \operatorname{dist}(F)=3

这说明了 BFS 最重要的价值。BFS 在距离为 $3$ 时到达 $F$ ，所以从 $A$ 到 $F$ 的最短路径需要经过 $3$ 条边。一条最短路径是 $A \to B \to D \to F$ ，另一条是 $A \to C \to E \to F$ 。

只有当每条边的代价都相同，或者把图看作无权图时，这才成立。如果边的权重不同，BFS 可能会找到一条边数更少、但总成本更高的路径。

在标准 BFS 中，节点通常是在入队时就被标记为已访问，而不是等到之后出队时再标记。这样可以避免同一个节点被重复加入队列很多次。

BFS 是按层探索。深度优先搜索（DFS）则会沿着一条分支不断深入，直到需要回溯。它们各自更适合回答不同类型的问题。

同一层内部的精确访问顺序，可能会因为邻居的列出顺序不同而变化。距离上的保证仍然成立，但遍历顺序可能不同。

当你关心可达性、树中的层序遍历，或者按边数计算的最短路径长度时，BFS 非常有用。

它也常见于状态空间问题中，前提是每一步移动的代价都相同。在这种条件下，BFS 往往是寻找最少步数的最清晰方法。

可以把 BFS 想成从起始节点向外扩散的波纹。每扩散一层，距离就多一条边。

如果你想自己试一试，可以画一张小图，选一个起始节点，并在每一步后写下队列的内容。如果你还想继续，可以做一道类似的图遍历题，并检查当图变成带权图时，最短路径这个结论是否仍然成立。

上传你的问题，几秒钟内获得经过验证的分步解答。