第09章 图算法：最短路、网络流与最小生成树

这一篇在干嘛？

路网导航、任务调度、网络布线、社交关系——凡是”东西之间有连接”的建模都是图。本章覆盖面试与工程最高频的四组算法：拓扑排序（依赖排序）、Dijkstra（最短路）、Prim/Kruskal（最小生成树）、DFS 家族（割点/欧拉回路/强连通分量），最后认识一下 NP 完全性这道”算法天花板”。

9.1 定义与存储

图 $G=(V,E)$：顶点集 + 边集。有向/无向、带权/无权。路径是顶点序列；环是起点终点相同的路径；无环的有向图叫 DAG。连通、强连通等概念见文中。

邻接矩阵：$N\times N$ 布尔矩阵，查边 $O(1)$，空间 $O(N^2)$——稠密图适用。邻接表：每个顶点挂一条”出边链表”，空间 $O(|E|+|V|)$——稀疏图（多数现实场景）的标准选择，本章算法默认它。

白话：路网、社交网络都是巨大的稀疏图（人均好友数远小于人口数），邻接矩阵会浪费 99.9% 的空间。选型一句话：边多到接近 $N^2$ 用矩阵，否则用表。

9.2 拓扑排序：给依赖排个序

问题：课程先修关系（修数据结构前要先学程序设计）排成一个合法学习顺序。有向无环图（DAG）的拓扑序：所有边都”从左指向右”。

算法（Kahn / 入度法）：入度为 0 的顶点进队列 → 出队一个，输出它，并把它指向的所有顶点入度 −1 → 新的入度 0 顶点入队。循环直到队列空。

void topsort() {
    Queue<Vertex> q;
    int counter = 0;
    for each Vertex v
        if (v.indegree == 0)
            q.enqueue(v);
    while (!q.isEmpty()) {
        Vertex v = q.dequeue();
        v.topNum = ++counter;            // 拓扑序号
        for each Vertex w adjacent to v
            if (--w.indegree == 0)
                q.enqueue(w);
    }
    if (counter != NUM_VERTICES)
        throw CycleFoundException{};     // 没处理完 = 有环
}

白话：入度 = “还有几门先修课没上”。归零即解锁，解锁即上课（出队），上课又解锁后继。如果最后没有全部出队，剩下的一定构成环——拓扑排序顺带就是环检测器。$O(|E|+|V|)$。

9.3 无权最短路：BFS 就是答案

问题：单源最短路——从 $s$ 出发到每点的最少边数。按”离 s 的距离”分层：距离 d 的顶点只可能从距离 d−1 的顶点走来——这正是队列的先进先出：

void unweighted(Vertex s) {
    Queue<Vertex> q;
    for each Vertex v  v.dist = INFINITY;
    s.dist = 0;
    q.enqueue(s);
    while (!q.isEmpty()) {
        Vertex v = q.dequeue();
        for each Vertex w adjacent to v
            if (w.dist == INFINITY) {     // 第一次到达 = 最短
                w.dist = v.dist + 1;
                w.path = v;               // 记住从哪来（回溯路径用）
                q.enqueue(w);
            }
    }
}

path 指针构成一棵最短路树，从终点沿 path 回溯倒着打印就是路径。$O(|E|+|V|)$。

白话：无权图里”边数最少”和”先被水淹到”是一回事——从源头倒水（BFS），水波按距离一圈圈扩散，第一次淹到你的波就是最短路。

9.4 Dijkstra：带权最短路的标准解法

贪心策略：按距离从小到大逐个”敲定”顶点。已敲定的顶点距离绝不再改——前提是边权非负（负权会推翻贪心，见 9.5）。

void dijkstra(Vertex s) {
    for each Vertex v  { v.dist = INFINITY; v.known = false; }
    s.dist = 0;
    for (; ; ) {
        Vertex v = smallest unknown distance vertex;   // 取未定中最小的
        if (v == NOT_A_VERTEX) break;
        v.known = true;                                // 敲定
        for each Vertex w adjacent to v
            if (!w.known)
                if (v.dist + cvw < w.dist) {           // 经 v 中转更近？
                    w.dist = v.dist + cvw;             // 松弛
                    w.path = v;
                }
    }
}

复杂度看”取最小”用什么实现：

• 数组扫描取最小：$O(|V{|}^2)$——稠密图（$|E|\approx |V{|}^2$）最优。
• 二叉堆（第 6 章的主场）：取最小 $O(\log |V|)$、每次松弛可能 decreaseKey，总 $O(|E|\log |V|)$——稀疏图标准解。

白话：像滚雪球选最短——每一步都把”当前已知距离最小”的未定点收编（它的距离不可能再被绕路改善了，因为别的路都要经过更远的点）。收编后试着松弛邻居：“经过我到你会不会更近？“注意敲定后不再修改，这是与 Bellman-Ford 的本质区别。

9.5 负权边：Dijkstra 会翻车

Dijkstra 的贪心假设是”路只会越走越贵”。有负边时，一条”当前很远”的路径之后可能被负边拉回，已敲定的顶点作废——Dijkstra 直接失效。

Bellman-Ford：不设”敲定”，逐轮松弛所有边 $|V|-1$ 轮（最短路径至多 $|V|-1$ 条边，每轮至少敲定一条边）；$O(|E|\cdot |V|)$。第 $|V|$ 轮还能松弛 = 存在负权环，最短路无解（∞−∞ 问题）。

DAG 特例：先拓扑排序，按拓扑序松弛一遍即可——$O(|E|+|V|)$，又快又对（关键路径/PERT 图就用它）。

全源最短路（Floyd-Warshall）：所有点对最短路，动态规划 $d[i][j]=\min (d[i][j],d[i][k]+d[k][k])$ 三重循环 $O(|V{|}^3)$，代码仅 4 行，稠密图合适。

9.6 网络流：管道最大运输量

问题：有向图每条边有容量，从源点 $s$ 到汇点 $t$ 最多能”运”多少流量？约束：边上流量 ≤ 容量，除 s/t 外流入 = 流出。

基础算法：不断在残余图（residual graph：剩余容量 + 反向边）里找 s→t 的增广路径推流，直到无路可走。关键在反向边：允许”反悔”——后发现的更优路径可以把之前推的流顶回去。

白话：网络流是”退路的艺术”——朴素贪心推流可能堵死最优解，反向边给了流”改道”的权利。最大流 = 最小割（对偶定理），这也是很多组合优化问题的通用思路。本书只做入门，实践推荐 Dinic 等更快的算法。

9.7 最小生成树（MST）：布线的最省钱方案

问题：无向连通带权图，选 $|V|-1$ 条边把所有点连通且总权最小。贪心都成立（MST 有切割性质保证）：挑全局最小可用边绝不会错。

Prim：像 Dijkstra 一样长一棵树

从任一起点出发，反复把”离树最近的未收点”连进来。实现与 Dijkstra 同构（把 dist 定义从”距源点”换成”距树”），堆版 $O(|E|\log |V|)$。

Kruskal：从全局挑最便宜的边

所有边按权排序，从小到大扫描：两端不在同一集合就选（成环就跳过）——判环用第 8 章的并查集，$O(|E|\log |E|)$：

白话：Prim 是”滚雪球”（树一圈圈长大），Kruskal 是”捡便宜”（全图边从便宜到贵扫，不成环就买）。稀疏图选 Kruskal（排序主导、实现短），稠密图选 Prim。

9.8 DFS 的四大应用

深度优先搜索：一条路走到黑，撞墙回退。$O(|E|+|V|)$，用栈（递归）。

① 无向图判环：DFS 中遇到”已访问且不是父亲”的邻居 → 有环。

② 割点与双连通：割点（articulation point）= 删掉它图就不连通的顶点：

DFS 给顶点编号 Num，并维护 Low（该点或其后代经一条回边能到达的最小 Num）。割点判据：根节点有 ≥2 个孩子，或非根节点存在孩子满足 Low(child) ≥ Num(u)。

③ 欧拉回路：每条边恰好走一次回到起点。存在条件：连通且每个顶点度数为偶数（进一次必出一次）。算法：从任一点出发随手走（用掉的边删除），走不动了就地”拼接”别的环路——线性时间。

白话：欧拉回路的直觉是”一笔画回到原点”——每个访问点都被进/出配对，所以度数必须全是偶数。哥尼斯堡七桥问题的答案就是”没有”。

④ 强连通分量（SCC）：有向图中互相可达的最大点集。Kosaraju 两遍 DFS：① 对 G 做 DFS 并按后序编号压栈；② 在反图 $G_r$ 上按栈序（后序大的先）再做 DFS，每一棵 DFS 森林就是一个 SCC。

白话：反图上跑 DFS 相当于”从 SCC 出不去”变成”从外面进不来”——两遍下来把互相咬合的团块完整剥出来。直觉可自证，严谨证明看原书 9.6.5。

9.9 NP 完全性：知道天花板在哪

P：多项式时间可解的问题。NP：多项式时间可验证解的问题（解拿来看一眼对不对很快）。P ⊆ NP；“P = NP?”是悬赏百万美元的世纪难题。

NP 完全（NPC）：NP 中”最难”的一批问题，互相可多项式归约，只要任何一个有多项式算法，全部问题都迎刃而解。旅行商（TSP）、哈密顿回路、装箱、图着色等都是。识别出 NPC 问题的意义：别再徒劳地找多项式精确解，转攻近似算法、启发式、随机化或利用输入的特殊结构（第 10 章的回溯就干这个）。

常见坑

① 负权图用 Dijkstra：贪心前提被破坏，结果错——换 Bellman-Ford 或先拓扑排序（DAG）。② 拓扑排序忘了环检测：counter 没走满就说明有环，直接当排序成功会静默输出垃圾。③ Kruskal 判环不用并查集而自己 DFS：每次判环 O(N)，复杂度爆炸——并查集一次近 O(1)。④ DFS 求割点时 Low 用两条以上回边：Low 的定义只允许一条回边，取多了会把割点漏判。

通关标准

学完本篇你应该能做到：① 手写拓扑排序并顺带判环；② 手写 BFS 无权最短路和 Dijkstra 主循环，说清堆版复杂度 $O(|E|\log |V|)$；③ 讲清负权边为什么破坏 Dijkstra、Bellman-Ford 如何兜底；④ 写出 Kruskal（配并查集）并对比 Prim；⑤ 用 Low/Num 找割点、判欧拉回路条件、描述 Kosaraju 两遍 DFS；⑥ 判断给定问题是 P 还是 NPC 并决定攻防策略。

Dijkstra 为什么"敲定"过的点不再修改？这个前提何时失效？

非负权下，任何绕路都经过”距离 ≥ 当前最小”的点，不可能比已敲定值更小。负边让”先远后负”成为可能，敲定值可能被拉低——前提失效，需改用 Bellman-Ford。

拓扑排序的队列换成栈可以吗？换成任意选点呢？

可以——任何”入度为 0 就处理”的顺序都合法，队列/栈只是遍历风格不同；手动任选入度 0 的点也行。唯一的硬约束是无环。

Prim 和 Dijkstra 代码几乎一样，本质区别是什么？

dist 的含义：Dijkstra 是”距源点的路径总长”（累加边权）；Prim 是”距生成树的最短一条边”（单边权）。所以 Prim 的贪心是切割性质保证、对负权也不敏感，Dijkstra 则不行。

欧拉回路和哈密顿回路都是"转一圈"，为什么难度天壤之别？

欧拉回路只关心边，度数全是偶数即可判定（多项式，甚至线性算法）。哈密顿回路关心点的全局排列，是 NP 完全的——一字之差，可解与不可解的分界。

Kosaraju 算法为什么要在反图上跑第二遍 DFS？

第一遍的后序保证”最上游的 SCC 先入栈”。反图上从该点 DFS，恰好只能访问该 SCC 内部（SCC 内互相可达不受反向影响，跨 SCC 的边反向后被”堵住”），从而精确剥离一个分量。