十一、网络流与最小生成树
考点速览
| # | 考点 | 题型 | 重要度 |
|---|---|---|---|
| 1 | 最大流定义与流量守恒 | 填空 / 选择 | ★★★ |
| 2 | 残余图 \(G_r\) 的构造（含反向边） | 画图 / 大题 | ★★★★★ |
| 3 | 增广路径迭代求最大流 | 大题（手算） | ★★★★★ |
| 4 | 贪心选第一条路径为何错 | 简答 | ★★★ |
| 5 | 增广算法的三种复杂度 | 填空 / 选择 | ★★★★ |
| 6 | Prim 算法手算 | 大题（画 MST） | ★★★★★ |
| 7 | Kruskal 算法手算 + 并查集判环 | 大题 | ★★★★★ |
| 8 | Prim vs Kruskal 复杂度选择 | 选择 | ★★★ |
| 9 | 生成树的基本性质（边数 / 加边成环） | 填空 | ★★★ |
§4 网络流问题（Network Flow Problems）
考点 1：问题定义与守恒约束
给定有向图 \(G\)：
- 源点 \(s\)：只有流出
- 汇点 \(t\)：只有流入
- 每条边 \((v, w)\) 有容量 \(c_{v,w}\)
流量守恒：对所有 \(v \notin \{s, t\}\)，
目标：求 \(s \to t\) 能通过的最大流量。
易错点
- 容量是边的属性，不是顶点的属性。
- 守恒不包括 \(s\) 和 \(t\)；\(s\) 流出量 = \(t\) 流入量 = 当前流值 \(f\)。
考点 2 + 3：Ford-Fulkerson 算法（FF 算法）
这就是 PPT 中讲的那套"残余图 + 增广路径"方法，学术名称为 Ford-Fulkerson Method。
三个图——一图看懂
原始图 G 流图 Gf 残余图 Gr
(标的是容量) (标的是已用流) (标的是还能走多少)
s ──3──▶ a s ──2──▶ a s ──1──▶ a ← 正向剩余
│ │ │ │ │ │
2 2 0 2 2 0
▼ ▼ ▼ ▼ ▼ ▼
b ──3──▶ t b ──0──▶ t b ──3──▶ t
a ──2──▶ s ← 反向边！
t ──2──▶ a ← 反向边！
| 符号 | 含义 | 边上标什么 |
|---|---|---|
| \(G\) | 原始图 | 容量 \(c_{v,w}\) |
| \(G_f\) | 流图 | 当前已分配的流 \(f_{v,w}\) |
| \(G_r\) | 残余图 | 正向 \(c-f\)，反向 \(f\)（可撤销量） |
残余图构造规则（考试必考 ★★★★★）
对原图中每一条有向边 \((v, w)\)：
三条铁律：
- 正向残余 = \(c_{v,w} - f_{v,w}\)（还能再走多少）
- 反向残余 = \(f_{v,w}\)（已用流 = 可撤回量）
- 残余为 0 的边删掉
FF 算法步骤（背下来）
Ford-Fulkerson(G, s, t):
初始化所有边 f = 0
while (Gr 中存在 s→t 的路径 P): ← 增广路径
Δ = min(P 上所有边的残余容量) ← 瓶颈
for P 上每条边 (u,v):
if (u,v) 是正向边: f(u,v) += Δ
if (u,v) 是反向边: f(v,u) -= Δ ← 撤销
更新 Gr
return 当前总流值
完整例题走查：一步步跑 FF 算法
原图 \(G\)（5 条边，4 个节点）：
| 边 | 容量 |
|---|---|
| s→a | 1 |
| s→b | 1 |
| a→b | 1 |
| a→t | 1 |
| b→t | 1 |
最大流应该 = 2（很直观：\(s \to a \to t\) 走 1，\(s \to b \to t\) 走 1）。
❌ 如果不加反向边（纯贪心）
第 1 轮：贪心选了 \(s \to a \to b \to t\)，\(\Delta = 1\)
第 2 轮：找 \(s \to t\) 的路径...
- \(s \to b \to ?\)：\(b \to t\) 已满！
- \(s \to a\)：已满！
卡住了！总流 = 1 ≠ 正确答案 2。
✅ 加反向边（正确的 FF 算法）
第 1 轮：同样选 \(s \to a \to b \to t\)，\(\Delta = 1\)
残余图 Gr（有反向边版本）:
s
\
(1) s→b 剩余
↓
┌──▶ b ←─(1)── a ← 反向边 b→a 出现了！
|
(1) | a→s: (1) ← 反向边
| t→b: (1) ← 反向边
| a→t: (1) ← a→t 从未用过
↓
无（b→t 已满）
整理残余图 Gr 的边：
s→b: 1（未用过）
a→t: 1（未用过）
a→s: 1（反向，s→a 的撤销边）
b→a: 1（反向，a→b 的撤销边）
t→b: 1（反向，b→t 的撤销边）
第 2 轮：在 \(G_r\) 中找 \(s \to t\)：
注意：\(b \to a\) 是反向边！走它意味着撤销之前 \(a \to b\) 的那 1 单位流。
\(\Delta = \min(1, 1, 1) = 1\)
更新后的流图 \(G_f\)：
s 解读：
/ \ • s→a: 流 1（未变）
f=1 f=1 • s→b: 流 1（新增）
↓ ↓ • a→b: 流 0（被撤销了！）
a b • a→t: 流 1（新增）
| | • b→t: 流 1（未变）
f=1 f=1
↓ ↓
t
总流 = 2 ✓（\(s\) 流出 \(1+1=2\)，\(t\) 流入 \(1+1=2\)）
核心直觉
走反向边 \(b \to a\) = 把之前走错的 \(a \to b\) 退回来，让 \(a\) 的流量改道去 \(t\)，让 \(b\) 的流量由 \(s\) 直接供给。
考点 4：为什么必须加反向边
| 无反向边（纯贪心） | 有反向边（FF 算法） | |
|---|---|---|
| 第一次选错了怎么办 | 死了，无法纠正 | 走反向边 = 撤销 |
| 上面例子结果 | 流 = 1（错） | 流 = 2（对） |
| 本质 | 一条路走到黑 | 允许「后悔」 |
定理（必背）
若所有边容量为有理数，Ford-Fulkerson 算法必终止且得到最大流。
对含环图同样成立。
易错点
- 反向边的容量 = 当前已用流量，不是 0，也不是原容量。
- 同一条原边可以同时在 \(G_r\) 中有正向 + 反向两个身份（部分用了部分没用时）。
- 走反向边后，对应的正向流量要减少（撤销），不是增加。
考点 5：复杂度分析（填空 / 选择高频）
FF 算法的效率取决于怎么选增广路径：
| 策略 | 选法 | 增广次数上限 | 单次找路 | 总复杂度 |
|---|---|---|---|---|
| 任意路径 | DFS/随便 | \(O(f)\)（\(f\)=最大流值） | \(O(\|E\|)\) | \(O(f \cdot \|E\|)\) |
| 最大瓶颈路径 | 改造 Dijkstra | \(O(\|E\| \log cap_{\max})\) | \(O(\|E\| \log \|V\|)\) | \(O(\|E\|^2 \log \|V\|)\) |
| 最短路径（BFS） | BFS | \(O(\|E\| \cdot \|V\|)\) | \(O(\|E\|)\) | \(O(\|E\|^2 \|V\|)\) |
↑ 第三行就是 Edmonds-Karp 算法——FF 的 BFS 实现版本，复杂度与 \(f\) 无关，保证多项式时间终止。
最坏情况举例
边容量为 \(10^6\) 时，任意路径策略可能增广 \(2 \times 10^6\) 次——每次只增 1！
特殊情况
若每个 \(v \notin \{s, t\}\) 要么只有一条容量 1 的入边，要么只有一条容量 1 的出边，则 \(T = O(|E| \cdot |V|^{1/2})\)。
最小费用流（Min-Cost Flow）
所有最大流中找总费用最小的——每条边附带单位流量费用。
§5 最小生成树（Minimum Spanning Tree）
考点 9：定义与基本性质（填空必考）
生成树：图 \(G\) 的一棵树，包含 \(G\) 的全部顶点和部分边。
最小生成树（MST）：边权和最小的生成树。
| 性质 | 内容 |
|---|---|
| 边数 | 恰为 \(\|V\| - 1\) |
| 结构 | 树（无环），覆盖所有顶点 |
| 存在性 | \(G\) 必须连通 |
| 加边性质 | 向 MST 加入任意一条非树边 → 必形成唯一一个环 |
贪心约束（解题前默念）：
- 只能用图中已有的边；
- 必须恰好 \(|V| - 1\) 条边；
- 不能选会成环的边。
考点 6：Prim 算法 —— 生长一棵树
与 Dijkstra 几乎一致，区别仅在更新公式（用边权本身，不累加）。
解题步骤（手算模板）
1. 任选起点 \(s\)，加入 \(T\)。
2. 在所有"一端在 \(T\) 内、一端在 \(T\) 外"的边中选权值最小的边 \((u, v)\)。
3. 把 \(v\) 和边 \((u, v)\) 加入 \(T\)。
4. 回到步骤 2，直到 \(T\) 中有 \(|V|\) 个顶点。
void Prim(Graph G, Vertex s)
{
将 s 加入树 T；
while (T 中顶点数 < |V|) {
在所有一端在 T 内、一端在 T 外的边中，
选权值最小的边 (u, v)；
将 v 加入 T，将边 (u, v) 加入 T；
}
}
复杂度（与 Dijkstra 同）：二叉堆实现为 \(O(|E| \log |V|)\)。
易错点
Prim 维护的是一棵正在长大的树——任何时刻只有一个连通块。和 Kruskal 的"森林"对照记忆。
考点 7：Kruskal 算法 —— 维护一个森林
思想：边按权值从小到大排序，依次考察，不成环就加入。
解题步骤（手算模板）
1. 所有边按权值升序排列。
2. 取出当前最小边 \((v, w)\)。
3. 用并查集判：\(v\) 和 \(w\) 是否已在同一连通块？
• 否 → 加入 \(T\)，合并 \(v\) 与 \(w\) 所在集合（Union）。
• 是 → 丢弃。
4. 重复直到 \(T\) 中已有 \(|V| - 1\) 条边，或边集空。
5. 若结束时仍不足 \(|V| - 1\) 条边 → 报错"No spanning tree"（图不连通）。
void Kruskal(Graph G)
{ T = { };
while (T contains less than |V| - 1 edges
&& E is not empty) {
choose a least cost edge (v, w) from E; /* DeleteMin */
delete (v, w) from E;
if ((v, w) does not create a cycle in T)
add (v, w) to T; /* Union / Find */
else
discard (v, w);
}
if (T contains fewer than |V| - 1 edges)
Error("No spanning tree");
}
复杂度拆解
| 子步骤 | 数据结构 | 复杂度 |
|---|---|---|
| 排序 / 取最小边 | 优先队列（DeleteMin） | \(O(\log \|E\|)\) 每次 |
| 判环 / 合并 | 并查集（Union / Find） | 近似 \(O(1)\) 每次 |
易错点
"不成环"必须用并查集判，不能用 visited 数组——Kruskal 中点是分散的多个集合。
考点 8：Prim vs Kruskal 横向对比
| 维度 | Prim | Kruskal |
|---|---|---|
| 视角 | 长一棵树 | 维护一片森林 |
| 数据结构 | 二叉堆（点） | 并查集 + 优先队列（边） |
| 复杂度 | \(O(\|E\| \log \|V\|)\) | \(O(\|E\| \log \|E\|)\) |
| 适用 | 稠密图（边多） | 稀疏图（边少） |
| 类比 | 类似 Dijkstra | 类似排序 + 并查集 |
速记
- 想问"和 Dijkstra 像吗？"→ Prim。
- 想问"用并查集吗？"→ Kruskal。