11.3 广度优先、深度优先与最短路径

第 11.2 节通过不断从已到达顶点向外扩张，找到了一个连通分量。真正的算法还要做一个选择：当多个已到达顶点仍有未探索邻居时，下一步处理谁？

两种不同答案会产生广度优先搜索和深度优先搜索。它们最终都能到达起点所在分量中的全部顶点，但探索形状不同。

搜索状态：已发现、已处理与前沿

固定起点 $s$。搜索过程中，可以把每个顶点理解为三种状态之一：

• 未发现：搜索还没有到达；

• 已发现：已经到达，但可能尚未检查完所有邻居；

• 已处理：所有邻居都已经检查。

前沿保存等待处理的已发现顶点。一个顶点第一次进入前沿时就应标记为已发现，而不能等到它离开前沿时再标记；否则两个顶点可能重复加入同一个邻居。

当顶点 $v$ 第一次由 $u$ 发现时，把 $u$ 记录为它的前驱，写作 $\operatorname{pred}(v)=u$。所有前驱边会形成一棵以 $s$ 为根的搜索树。这不表示原图是树；搜索树只记录每个顶点第一次被发现的路线。

为了让追踪结果可以复现，下面按照字母顺序检查每张邻接表。改变邻居顺序可能产生另一棵同样正确的搜索树。

广度优先搜索使用队列

队列遵守“先进先出”：最早加入的元素最先离开。广度优先搜索（Breadth-First Search，BFS）用队列保存前沿。

从 $s$ 出发：

1. 把 $s$ 标记为已发现并加入队列；

2. 取出队首顶点 $u$；

3. 检查 $u$ 的每个邻居 $v$；

4. 若 $v$ 尚未发现，就标记它，令 $\operatorname{pred}(v)=u$，并把它加入队尾；

5. 把 $u$ 标记为已处理，重复执行，直到队列为空。

考虑如下邻接表：

从 $A$ 开始的 BFS 过程为：

最终得到的分层是

$L_i$ 中的每个顶点，到 $A$ 的最短路径都恰好包含 $i$ 条边。

为什么 BFS 能找到无权最短路径

在无权图中，距离 $d(s,v)$ 是从 $s$ 到 $v$ 的所有路径中最少的边数。若不存在路径，就定义 $d(s,v)=\infty$。

BFS 会先处理所有距离为 $i$ 的顶点，然后才处理距离为 $i+1$ 的顶点。当 $L_i$ 中的顶点第一次发现 $v$ 时，得到一条长度为 $i+1$ 的路径。如果存在更短路径，那么 $v$ 应当早已从更前面的层被发现，产生矛盾。

从终点沿前驱指针反向追踪，可以恢复最短路径：

最后把这个序列反转，就得到从 $s$ 到 $v$ 的路径。

深度优先搜索使用栈

栈遵守“后进先出”：最近加入的元素最先离开。深度优先搜索（Depth-First Search，DFS）使用显式栈，或者利用递归函数调用所形成的调用栈。

DFS 会沿一条路线尽可能深入。当当前顶点没有未发现邻居时，它会回溯到前一个顶点，再尝试下一个邻居。

对同一张图按字母顺序检查邻居，从 $A$ 出发的一种 DFS 发现顺序为

搜索先沿 $A\to B\to D$ 深入，然后回溯到 $B$，再沿 $B\to E\to F\to C$ 前进。DFS 能建立合法的搜索树，但一般不保证最短路径。本例中，DFS 经过很长的树路线才到达 $C$，尽管原图中存在边 $AC$。

当问题关注深层依赖结构时，DFS 很有用，例如检测环、排列先修依赖或探索谜题的每条分支。若目标是最少经过多少条无权边，BFS 更自然。

使用邻接表时的运行时间

第 5 章介绍过渐近运行时间。无论 BFS 还是 DFS，每个顶点至多被发现一次。邻接表会把每条无向边记录在两个端点的列表中，因此每条边至多检查两次。于是

若使用邻接矩阵，为每个已到达顶点检查所有可能邻居可能需要 $O(|V|^2)$ 时间，即使图很稀疏。数据表示会直接影响算法成本。

让 BFS 与 DFS 探索者在同一张网络中竞速：预测下一个被处理的顶点，检查实时队列或栈，回放回溯过程，并比较两棵搜索树与发现路线。

带权最短路径需要累计成本

BFS 最小化经过的边数。当不同边具有不同成本时，它不能保证总权重最小。两条权重分别为 $2$ 和 $3$ 的边合计成本为 $5$，反而小于一条权重为 $9$ 的边。

对带权路径

定义总权重

从 $s$ 到 $v$ 的带权距离，是所有 $s$ 到 $v$ 路径中最小的 $w(P)$。

暂定距离与松弛

当所有边权都非负时，Dijkstra 算法可以解决单源最短路径问题。

算法为每个顶点维护暂定距离 $d[v]$，表示目前已经找到的最小路线成本。初始时，

假设已经知道一条到 $u$、成本为 $d[u]$ 的路线，现在检查边 $uv$。经过 $u$ 到达 $v$ 的成本是 $d[u]+w(uv)$。更新操作

称为对边 $uv$ 进行松弛。如果第二个值更小，还要令 $\operatorname{pred}(v)=u$。

Dijkstra 算法的确定前沿

当一个顶点的暂定距离被宣布为最终答案时，称它已经确定。Dijkstra 算法反复执行：

1. 在未确定顶点中选择 $d[u]$ 最小的顶点 $u$；

2. 确定 $u$；

3. 松弛 $u$ 到每个未确定邻居的边；

4. 当所有可达顶点都已确定，或目标顶点已确定时停止。

考虑边及其权重

从 $A$ 开始。首先确定 $A$，得到 $d[B]=4,d[C]=1$。接着确定 $C$；松弛 $CB$ 后，$d[B]$ 从 $4$ 改进到 $3$，边 $CD$ 给出 $d[D]=6$。然后确定 $B$；边 $BD$ 又把 $d[D]$ 从 $6$ 改进为 $4$。最后确定 $D$，得到 $d[E]=7$。

$E$ 的前驱链为

所以一条最短路径是 $A,C,B,D,E$，总权重为 $1+2+1+3=7$。

为什么边权必须非负

Dijkstra 确定暂定距离最小的顶点 $u$ 时，任何尚未发现完整答案的路线都要先进入某个未确定顶点，其暂定成本不小于 $d[u]$。后续边权非负，就不可能再把成本降到 $d[u]$ 以下。

负权边会破坏这个理由。之后才发现的路线可能通过负权边，变得比已经确定的路线更便宜。因此 Dijkstra 算法必须拒绝含负权边的图。其他算法可以处理某些负权图，但不属于本节范围。

简单的数组实现每轮扫描全部顶点，寻找暂定距离最小者，运行时间为 $O(|V|^2)$。优先队列是一种每次取出最小键值元素的数据结构；在稀疏图中使用优先队列可以避免反复扫描所有顶点。

在带权救援地图中调度路线：亲自选择要确定的暂定顶点和要松弛的边。地图会保留距离改进前后的标签，恢复前驱路线，并通过一次负权事故展示 Dijkstra 的保证为何失效。

选择合适的搜索

在无权图中，用 BFS 最小化边数；需要深入探索、回溯或观察结构依赖时使用 DFS；需要最小化非负边权总和时使用 Dijkstra。

第 11.4 节会改变优化的尺度。我们不再只寻找一条最短路线，而要选择一组没有冗余的边来连接全部顶点；在带权图中，还要让这些边的总代价最低。