02.12.2 网络流与二分图匹配
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.12 图与字符串进阶
覆盖范围
- 最大流 Ford-Fulkerson 与 Dinic
- 匈牙利算法二分图最大匹配
- KM 算法带权二分图
- 最小割最大流定理
高频题速览
| 编号 | 题目 | 难度 | 频率 |
|---|---|---|---|
| 02.12.2-001 | 最大流 Ford-Fulkerson | 高级 | ★★★ |
| 02.12.2-002 | Dinic 算法 | 高级 | ★★★ |
| 02.12.2-003 | 匈牙利算法二分图最大匹配 | 进阶 | ★★★★ |
| 02.12.2-004 | KM 算法带权二分图 | 高级 | ★★★ |
| 02.12.2-005 | 匈牙利 vs KM 区别 | 基础 | ★★★★ |
| 02.12.2-006 | 最小割最大流定理 | 进阶 | ★★★ |
| 02.12.2-007 | 二分图最小顶点覆盖 | 进阶 | ★★★ |
| 02.12.2-008 | 网络流应用场景 | 基础 | ★★★ |
02.12.2-001 最大流 Ford-Fulkerson
频率 ★★★ | 难度 高级
一句话结论
Ford-Fulkerson 反复在残量网络中找增广路,沿途增加流量;找不到增广路时当前流量即最大流;用 DFS 找增广路,时间复杂度 O(E * maxFlow)。
概念解释
- 残量网络:每条边有残量 capacity - flow。
- 增广路:从源点到汇点的路径,沿途残量 > 0。
- 反向边:用于退流,保证算法正确。
原理流程
- 建残量网络(正向边 + 反向边)。
- DFS 找增广路。
- 增广路上更新流量和残量。
- 找不到增广路时结束。
代码 / 示例
class Edge {
int to, rev, cap;
Edge(int to, int rev, int cap) { this.to = to; this.rev = rev; this.cap = cap; }
}
class FordFulkerson {
private final java.util.List<Edge>[] graph;
private final boolean[] visited;
private final int n;
FordFulkerson(int n) {
this.n = n;
graph = new java.util.List[n];
for (int i = 0; i < n; i++) graph[i] = new java.util.ArrayList<>();
visited = new boolean[n];
}
void addEdge(int from, int to, int cap) {
graph[from].add(new Edge(to, graph[to].size(), cap));
graph[to].add(new Edge(from, graph[from].size() - 1, 0));
}
int dfs(int u, int t, int flow) {
if (u == t) return flow;
visited[u] = true;
for (Edge e : graph[u]) {
if (!visited[e.to] && e.cap > 0) {
int d = dfs(e.to, t, Math.min(flow, e.cap));
if (d > 0) {
e.cap -= d;
graph[e.to].get(e.rev).cap += d;
return d;
}
}
}
return 0;
}
int maxFlow(int s, int t) {
int flow = 0;
while (true) {
java.util.Arrays.fill(visited, false);
int f = dfs(s, t, Integer.MAX_VALUE);
if (f == 0) break;
flow += f;
}
return flow;
}
}
常见误区
- 误区:不建反向边;正解:反向边用于退流,保证算法正确。
- 误区:DFS 用 BFS;正解:Ford-Fulkerson 用 DFS,Dinic 用 BFS 分层。
追问 / 延伸
- Q:时间复杂度? A:O(E * maxFlow),maxFlow 大时慢。
- Q:为什么需要反向边? A:退流,即之前增广的流量可以撤回,保证算法找到最优解。
02.12.2-002 Dinic 算法
频率 ★★★ | 难度 高级
一句话结论
Dinic 用 BFS 分层(构建 level graph),再用 DFS 在分层图中找阻塞流;重复直到汇点不可达;时间复杂度 O(V^2 * E),实际快很多。
概念解释
- BFS 分层:给每个节点分 level。
- 阻塞流:在分层图中尽可能多地增广。
- 重复:BFS 重建分层图,DFS 找阻塞流。
原理流程
- BFS 分层(只走残量 > 0 的边)。
- DFS 在分层图中找增广路(level[v] = level[u] + 1)。
- 重复直到汇点不可达。
代码 / 示例
class Dinic {
private final java.util.List<Edge>[] graph;
private final int[] level, iter;
private final int n;
Dinic(int n) {
this.n = n;
graph = new java.util.List[n];
for (int i = 0; i < n; i++) graph[i] = new java.util.ArrayList<>();
level = new int[n]; iter = new int[n];
}
void addEdge(int from, int to, int cap) {
graph[from].add(new Edge(to, graph[to].size(), cap));
graph[to].add(new Edge(from, graph[from].size() - 1, 0));
}
boolean bfs(int s, int t) {
java.util.Arrays.fill(level, -1);
java.util.Deque<Integer> q = new java.util.ArrayDeque<>();
level[s] = 0; q.offer(s);
while (!q.isEmpty()) {
int u = q.poll();
for (Edge e : graph[u]) {
if (e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[u] + 1;
q.offer(e.to);
}
}
}
return level[t] >= 0;
}
int dfs(int u, int t, int f) {
if (u == t) return f;
for (int i = iter[u]; i < graph[u].size(); i++) {
Edge e = graph[u].get(i);
if (e.cap > 0 && level[u] < level[e.to]) {
int d = dfs(e.to, t, Math.min(f, e.cap));
if (d > 0) {
e.cap -= d;
graph[e.to].get(e.rev).cap += d;
return d;
}
}
iter[u]++;
}
return 0;
}
int maxFlow(int s, int t) {
int flow = 0;
while (bfs(s, t)) {
java.util.Arrays.fill(iter, 0);
int f;
while ((f = dfs(s, t, Integer.MAX_VALUE)) > 0) flow += f;
}
return flow;
}
}
常见误区
- 误区:BFS 不分层;正解:BFS 分层,DFS 只走 level+1 的边。
- 误区:iter 不重置;正解:每次 BFS 后重置 iter。
追问 / 延伸
- Q:Dinic 时间复杂度? A:O(V^2 * E),实际远快。
- Q:单位容量网络? A:O(E * sqrt(V))。
02.12.2-003 匈牙利算法二分图最大匹配
频率 ★★★★ | 难度 进阶
一句话结论
二分图左部每个节点尝试找右部匹配;若右部节点已匹配,则尝试让已匹配的左部节点重新找其他右部;找到则增广,时间复杂度 O(V * E)。
概念解释
- 二分图:左部 L、右部 R,边只在 L-R 之间。
- 匹配:边集,任意两条边不共享端点。
- 增广路:从未匹配点出发,交替走非匹配边和匹配边,到未匹配点。
原理流程
- 对每个左部节点 u:
- DFS 尝试找右部节点 v。
- v 未匹配:直接匹配。
- v 已匹配:尝试让 v 的匹配左部节点重新找其他右部。
- 找到则增广。
代码 / 示例
class Hungarian {
private final java.util.List<Integer>[] graph; // 左部 -> 右部
private final int[] matchR; // 右部 -> 左部
private final boolean[] visited;
private final int n, m;
Hungarian(int n, int m) {
this.n = n; this.m = m;
graph = new java.util.List[n];
for (int i = 0; i < n; i++) graph[i] = new java.util.ArrayList<>();
matchR = new int[m];
java.util.Arrays.fill(matchR, -1);
visited = new boolean[n];
}
void addEdge(int u, int v) { graph[u].add(v); }
boolean dfs(int u) {
for (int v : graph[u]) {
if (!visited[v]) {
visited[v] = true;
if (matchR[v] == -1 || dfs(matchR[v])) {
matchR[v] = u;
return true;
}
}
}
return false;
}
int maxMatching() {
int count = 0;
for (int u = 0; u < n; u++) {
java.util.Arrays.fill(visited, false);
if (dfs(u)) count++;
}
return count;
}
}
常见误区
- 误区:visited 标记右部节点;正解:标记右部节点,防止重复尝试。
- 误区:matchR 初始化 0;正解:初始化 -1 表示未匹配。
追问 / 延伸
- Q:时间复杂度? A:O(V * E)。
- Q:最大匹配 = 最小顶点覆盖? A:二分图中成立(Konig 定理)。
02.12.2-004 KM 算法带权二分图
频率 ★★★ | 难度 高级
一句话结论
KM 求带权二分图最大权完美匹配;给左部节点顶标 l[u]、右部节点顶标 r[v],满足 l[u] + r[v] >= w(u,v);相等子图(l[u]+r[v]==w(u,v))的完美匹配即最大权匹配。
概念解释
- 顶标:左部 l[u]、右部 r[v]。
- 相等子图:l[u]+r[v] == w(u,v) 的边。
- 完美匹配:每个节点都匹配。
原理流程
- 初始化顶标:l[u] = max(w(u,v)),r[v] = 0。
- 对每个左部节点 u,在相等子图中找增广路。
- 找不到则调整顶标(降低左部、提高右部),扩大相等子图。
- 重复直到所有左部节点匹配。
代码 / 图示
KM 算法:
顶标 l[u], r[v],满足 l[u]+r[v] >= w(u,v)
相等子图:l[u]+r[v] == w(u,v)
相等子图完美匹配 = 最大权匹配
常见误区
- 误区:KM 求最大匹配;正解:KM 求最大权完美匹配。
- 误区:顶标初始化 0;正解:左部初始化为最大权边。
追问 / 延伸
- Q:时间复杂度? A:O(V^3)。
- Q:KM 和匈牙利区别? A:匈牙利求最大匹配(无权),KM 求最大权完美匹配(带权)。
02.12.2-005 匈牙利 vs KM 区别
频率 ★★★★ | 难度 基础
一句话结论
匈牙利求无权二分图最大匹配(最多匹配多少对);KM 求带权二分图最大权完美匹配(权值最大的完美匹配);两者都是二分图匹配,但目标不同。
概念解释
- 匈牙利:无权,最大匹配。
- KM:带权,最大权完美匹配。
- 复杂度:匈牙利 O(V*E),KM O(V^3)。
原理流程
- 只问最多匹配多少对:匈牙利。
- 问权值最大的完美匹配:KM。
- 两者都是增广路思想。
代码 / 图示
算法 目标 复杂度
匈牙利 最大匹配 O(V*E)
KM 最大权完美匹配 O(V^3)
常见误区
- 误区:KM 是匈牙利的带权版;正解:KM 用顶标和相等子图,思路不同。
- 误区:KM 求最大匹配;正解:KM 求最大权完美匹配。
追问 / 延伸
- Q:二分图最大匹配和最大流关系? A:二分图最大匹配 = 最大流(源点连左部、左部连右部、右部连汇点)。
- Q:KM 能求非完美匹配吗? A:可以,加虚拟节点。
02.12.2-006 最小割最大流定理
频率 ★★★ | 难度 进阶
一句话结论
最大流 = 最小割:残量网络中从源点到汇点的最大流等于把图分成 S(含源点)和 T(含汇点)的最小割(S-T cut 的容量和)。
概念解释
- 割:把节点分成 S 和 T,S 含源点,T 含汇点。
- 割容量:从 S 到 T 的边容量和。
- 最大流 = 最小割。
原理流程
- 求最大流。
- 残量网络中从源点 DFS,可达节点为 S。
- S 到 T 的边就是最小割。
代码 / 图示
最大流 = 最小割
S:源点可达节点
T:汇点不可达节点
S -> T 的边容量和 = 最大流
常见误区
- 误区:最小割是边数最少;正解:最小割是容量和最小。
- 误区:最大流和最小割无关;正解:最大流 = 最小割。
追问 / 延伸
- Q:最小割怎么求? A:最大流后,残量网络中源点可达节点为 S,S 到 T 的边。
- Q:最小割应用? A:最小点割、最大闭合权图。
02.12.2-007 二分图最小顶点覆盖
频率 ★★★ | 难度 进阶
一句话结论
二分图中,最小顶点覆盖(选最少的点覆盖所有边)= 最大匹配(Konig 定理);最大独立集 = 节点总数 - 最大匹配。
概念解释
- 顶点覆盖:选点集,每条边至少有一个端点在点集中。
- 最小顶点覆盖:最少点数。
- Konig 定理:二分图最小顶点覆盖 = 最大匹配。
原理流程
- 求最大匹配。
- 最小顶点覆盖 = 最大匹配。
- 最大独立集 = n - 最大匹配。
代码 / 图示
Konig 定理:
最小顶点覆盖 = 最大匹配
最大独立集 = n - 最大匹配
常见误区
- 误区:Konig 定理适用于所有图;正解:只适用于二分图。
- 误区:最大独立集 = 最大匹配;正解:最大独立集 = n - 最大匹配。
追问 / 延伸
- Q:最小顶点覆盖怎么求具体点? A:从左部未匹配点出发 DFS(交替路),左部未访问 + 右部已访问 = 最小顶点覆盖。
- Q:最大团? A:二分图中最大团 = 最大独立集。
02.12.2-008 网络流应用场景
频率 ★★★ | 难度 基础
一句话结论
网络流用于:二分图匹配、最大闭合权图、最小割(如项目选择)、多源多汇(加超级源汇)、最大密度子图;建模是关键。
概念解释
- 二分图匹配:源点连左部、右部连汇点。
- 最大闭合权图:选正权点和负权点,闭合集。
- 最小割:项目选择、最小点割。
原理流程
- 判断问题是否能转化为网络流。
- 建图(节点、边、容量)。
- 跑最大流。
- 从最大流结果提取答案。
代码 / 图示
应用:
二分图匹配 -> 最大流
项目选择 -> 最小割
最大闭合权图 -> 最小割
多源多汇 -> 超级源汇
常见误区
- 误区:网络流只能求最大流;正解:最小割、最大闭合权图等都是最大流的应用。
- 误区:网络流建模简单;正解:建模是难点,需要把问题转化为图。
追问 / 延伸
- Q:网络流工程中用得多吗? A:竞赛多,工程少,但某些调度问题用。
- Q:最大流和动态规划区别? A:网络流是图上的,DP 是序列上的。
待整理清单
- [ ] 最大闭合权图
- [ ] 费用流
- [ ] 上下界网络流