第14章：图算法(下)——最小生成树与最大流
本章目标
读完本章你会：
- 手写 Kruskal + Union-Find 和 Prim 算法
- 理解 MST 的贪心正确性——割性质和环性质
- 手写 Ford-Fulkerson 和 Edmonds-Karp 求最大流
- 理解 max-flow/min-cut 对偶性的含义和应用
- 用最大流解决二分图匹配
知识讲解
从一个生活例子开始
最小生成树 (MST)： 你要用最少的光缆连接 n 个城市。每条可能的连接有不同成本（地理条件不同）。
- Kruskal 的思路：从小到大试每根光缆，"这两个城市已经连上了吗？没连上就铺这根，连上了就跳过"。
- Prim 的思路：从任意城市开始，每次从"当前已连通的集合"到"外部"的最便宜光缆。
最大流： 城市之间的管道有不同的容量限制。从水源城市到用水城市，每秒最多能输送多少水？
关键发现：最大流量 = 最小切割容量（瓶颈）。如果能找到一条从水源到目的地的"瓶颈路"，那么它的容量就是全局上限。
工作原理
14.1 Kruskal 算法 + 并查集
KRUSKAL(G):将所有边按权重排序初始化并查集（每个节点自成一集合）for 每条边 (u, v) 按权重从小到大:if Find(u) ≠ Find(v): // u 和 v 不在同一个连通分量把边加入 MSTUnion(u, v) // 合并两个连通分量
并查集的核心操作：
Find(x)：返回 x 所在集合的代表元，路径压缩使后续 Find 近乎 O(1)Union(x, y)：合并两个集合，按秩合并保证树不退化
复杂度： O(E log E) = O(E log V)（排序主导），加上几乎线性的并查集操作。
为什么成立——割性质： 对任何割（把图分成两组节点），跨越割的最小权重边一定属于某个 MST。Kruskal 每次选的最小边就是一个割的最小跨越边。
14.2 Prim 算法
PRIM(G, start):dist[v] = ∞（v 距离已建成 MST 的最短距离）dist[start] = 0优先队列 Q 包含所有节点，按 dist 排序while Q 不为空:u = Q.pop_min() // 距离 MST 最近的节点for u 的每条邻边 (u, v, w):if v 在 Q 中 and w < dist[v]:dist[v] = wparent[v] = uQ.decrease_key(v, w)
复杂度： O(E log V)（二叉堆），或 O(E + V log V)（斐波那契堆——理论优势）。
Kruskal vs Prim 选择：
| Kruskal | Prim | |
|---|---|---|
| 适合 | 稀疏图 | 稠密图 |
| 数据结构 | 并查集 | 优先队列 |
| 实现难度 | 较简单 | 中等 |
| 边排序 | 必须 | 不需要 |
| 空间 | O(E) 存排序的边 | O(V) 优先队列 |
14.3 最大流：Ford-Fulkerson
核心概念：
- 流网络： 有向图，每条边 (u,v) 有容量 c(u,v)，流量 f(u,v) ≤ c(u,v)
- 守恒： 除源点 s 和汇点 t 外，每个节点流入 = 流出
- 剩余容量： c_f(u,v) = c(u,v) - f(u,v)（剩余可用容量）
- 增广路： 从 s 到 t 的路径，路径上所有边的剩余容量 > 0
FORD-FULKERSON(G, s, t):for 每条边: f(u,v) = 0while 存在从 s 到 t 的增广路 p:瓶颈 = min{c_f(u,v) : (u,v) 在 p 上}for 每条边 (u,v) 在 p 上:f(u,v) += 瓶颈f(v,u) -= 瓶颈 // 反向边——允许"撤销"流量
Edmonds-Karp 改进： 每次选最短（边数最少）的增广路——用 BFS 找。复杂度 O(V·E²)。
直觉——为什么反向边？ 想象两条路径争抢同一条管道的容量。一条路径先占满了管道，另一条路径可以通过反向边"推回"一部分流量，让两条路径都满意。反向边是实现"流量重分配"的机制。
14.4 Max-Flow/Min-Cut 对偶性
s-t 割： 将节点分成 S（含 s）和 T（含 t）的两组。割容量 = 所有从 S 跨到 T 的边的容量之和。
定理： 最大流的值 = 最小 s-t 割的容量。
应用——二分图最大匹配： 左组 L 到右组 R，每条边表示"可以配对"。建超级源 → L 所有节点（容量 1），R 所有节点 → 超级汇（容量 1）。最大流 = 最大匹配数。
代码实战
include/algo/graph_advanced.h
#ifndef ALGO_GRAPH_ADVANCED_H_
#define ALGO_GRAPH_ADVANCED_H_#include <cstdint>
#include <vector>namespace algo {// ========== Union-Find（并查集）==========
class UnionFind {public:explicit UnionFind(int n);int Find(int x);void Union(int x, int y);bool Connected(int x, int y);int Count() const { return count_; }private:std::vector<int> parent_;std::vector<int> rank_;int count_;
};// ========== 最小生成树 ==========
struct Edge {int u, v, weight;bool operator<(const Edge& other) const { return weight < other.weight; }
};// Kruskal：返回 MST 的边集合，若图不连通则返回空
std::vector<Edge> KruskalMST(int vertices, std::vector<Edge> edges);// Prim：返回 MST 的总权重（用优先队列实现）
int64_t PrimMST(const std::vector<std::vector<std::pair<int, int>>>& adj);// ========== 最大流 (Edmonds-Karp) ==========
class MaxFlow {public:MaxFlow(int vertices);void AddEdge(int from, int to, int64_t capacity);int64_t Compute(int source, int sink);private:int V_;struct FlowEdge {int to, rev; // 目标节点和反向边索引int64_t cap, flow;};std::vector<std::vector<FlowEdge>> adj_;
};} // namespace algo#endif // ALGO_GRAPH_ADVANCED_H_
include/algo/graph_advanced_impl.h（Kruskal + MaxFlow）
namespace algo {// ========== UnionFind ==========
inline UnionFind::UnionFind(int n) : parent_(n), rank_(n, 0), count_(n) {for (int i = 0; i < n; ++i) parent_[i] = i;
}inline int UnionFind::Find(int x) {if (parent_[x] != x) parent_[x] = Find(parent_[x]); // 路径压缩return parent_[x];
}inline void UnionFind::Union(int x, int y) {int rx = Find(x), ry = Find(y);if (rx == ry) return;// 按秩合并if (rank_[rx] < rank_[ry]) std::swap(rx, ry);parent_[ry] = rx;if (rank_[rx] == rank_[ry]) ++rank_[rx];--count_;
}inline bool UnionFind::Connected(int x, int y) { return Find(x) == Find(y); }// ========== Kruskal ==========
inline std::vector<Edge> KruskalMST(int vertices, std::vector<Edge> edges) {std::sort(edges.begin(), edges.end());UnionFind uf(vertices);std::vector<Edge> mst;for (auto& e : edges) {if (!uf.Connected(e.u, e.v)) {uf.Union(e.u, e.v);mst.push_back(e);if (static_cast<int>(mst.size()) == vertices - 1) break;}}if (static_cast<int>(mst.size()) != vertices - 1) return {}; // 不连通return mst;
}// ========== Edmonds-Karp ==========
inline MaxFlow::MaxFlow(int vertices) : V_(vertices), adj_(vertices) {}inline void MaxFlow::AddEdge(int from, int to, int64_t capacity) {// 正边：from → to，容量 capacityadj_[from].push_back({to, static_cast<int>(adj_[to].size()), capacity, 0});// 反边：to → from，容量 0（初始），rev 指向正边在 adj_[from] 中的位置// rev = adj_[from].size() - 1 因为正边刚刚被 push_back 到 adj_[from] 的末尾adj_[to].push_back({from, static_cast<int>(adj_[from].size()) - 1, 0, 0});
}inline int64_t MaxFlow::Compute(int source, int sink) {int64_t total_flow = 0;while (true) {// BFS 找最短增广路std::vector<int> parent(V_, -1);std::vector<int> edge_idx(V_, -1);std::queue<int> q;q.push(source);while (!q.empty() && parent[sink] == -1) {int u = q.front(); q.pop();for (int i = 0; i < static_cast<int>(adj_[u].size()); ++i) {auto& e = adj_[u][i];if (parent[e.to] == -1 && e.cap > e.flow) {parent[e.to] = u;edge_idx[e.to] = i;q.push(e.to);}}}if (parent[sink] == -1) break; // 没有增广路了// 找瓶颈int64_t bottleneck = std::numeric_limits<int64_t>::max();for (int v = sink; v != source; v = parent[v]) {int u = parent[v];auto& e = adj_[u][edge_idx[v]];bottleneck = std::min(bottleneck, e.cap - e.flow);}// 增广for (int v = sink; v != source; v = parent[v]) {int u = parent[v];auto& e = adj_[u][edge_idx[v]];e.flow += bottleneck;adj_[e.to][e.rev].flow -= bottleneck;}total_flow += bottleneck;}return total_flow;
}} // namespace algo
本章小结
- Kruskal 通过排序 + 并查集贪心构建 MST，O(E log E)；Prim 通过优先队列，O(E log V)
- MST 贪心正确性由割性质和环性质保证
- Ford-Fulkerson 通过反复找增广路求最大流；Edmonds-Karp 用 BFS 保证最坏 O(V·E²)
- 最大流的值 = 最小 s-t 割的容量——这一定理连接了流和割两个概念
- 并查集的两大优化：路径压缩（Find 近乎 O(1)）和按秩合并（保持树平衡）
关键术语
| 术语 | 释义 |
|---|---|
| MST | 最小生成树——连接所有节点的最小总成本无环子图 |
| 并查集 | 维护不相交集合的数据结构，近乎 O(1) 的 Find 和 Union |
| 增广路 | 剩余网络中从源到汇的可达路径——增大流量 |
| 最小割 | 将图分成 S(含源)和 T(含汇)的最小总容量划分 |
| 反向边 | 允许"撤销"已分配流量——Ford-Fulkerson 正确性的核心 |