图论算法（五）：网络流与二分图匹配
写在前面
网络流是图论中一个极具实用价值的分支，它研究的是在带权有向图中，从源点流向汇点的最大流量问题。网络流模型广泛应用于物流运输、电路设计、任务调度、图像分割等领域。与之密切相关的二分图匹配则解决“如何为两类对象建立最佳配对”的问题。
阅读指南：本文包含👇
-
最大流：Ford-Fulkerson、Edmonds-Karp、Dinic 算法
-
最小割：最大流最小割定理
-
二分图匹配：匈牙利算法、KM 算法
-
流程图：流程图片
-
代码实现：带详细注释
-
LeetCode实战：典型例题+解题代码
一、网络流基础概念
流网络是一个有向图 G=(V,E)G=(V,E)，其中每条边 (u,v)(u,v) 有一个非负容量 c(u,v)c(u,v)。图中指定两个特殊顶点：源点 ss 和汇点 tt。一个流 ff 是一个从边到非负实数的函数，满足：
-
容量限制：0≤f(u,v)≤c(u,v)0≤f(u,v)≤c(u,v)
-
流量守恒：对除 s,ts,t 外的所有顶点，流入量等于流出量
最大流问题：从 ss 到 tt 输送的最大总流量。
最小割：将顶点集划分为包含 ss 的集合 SS 和包含 tt 的集合 TT，割的容量为从 SS 到 TT 的所有边的容量之和。最大流最小割定理：最大流的流量等于最小割的容量。
二、最大流算法
1️⃣ Ford-Fulkerson 方法（增广路思想）
🎯 一句话记住
不停地找能从源点到汇点的增广路，直到再也找不到。
🤔 核心思想
Ford-Fulkerson 是最大流算法的通用框架：在残余网络中反复寻找从 ss 到 tt 的增广路径（一条可以增加流量的路径），然后沿着该路径增加流量，直到不存在增广路径为止。该方法的正确性依赖于残余网络的概念——每次增广后，在原边的反方向增加一条容量等于增广量的反向边，用于“反悔”。
📊 流程图
-
Ford-Fulkerson 动态演示（VisuAlgo，新加坡国立大学官方教学工具，可逐步动画演示）
💻 代码实现（DFS 版，最简实现）
/**
* Ford-Fulkerson 算法（基于 DFS）
* @param {number} n 顶点数（0~n-1）
* @param {number[][]} graph 邻接矩阵容量
* @param {number} s 源点
* @param {number} t 汇点
* @returns {number} 最大流
*/
function fordFulkerson(n, graph, s, t) {
const residual = graph.map(row => [...row]);
const parent = new Array(n).fill(-1);
let maxFlow = 0;
const dfs = (u, flow) => {
if (u === t) return flow;
for (let v = 0; v < n; v++) {
if (parent[v] === -1 && residual[u][v] > 0) {
parent[v] = u;
const newFlow = Math.min(flow, residual[u][v]);
const result = dfs(v, newFlow);
if (result > 0) {
residual[u][v] -= result;
residual[v][u] += result;
return result;
}
}
}
return 0;
};
while (true) {
parent.fill(-1);
parent[s] = s;
const pathFlow = dfs(s, Infinity);
if (pathFlow === 0) break;
maxFlow += pathFlow;
}
return maxFlow;
}🏆 LeetCode 例题
LeetCode 上直接考查最大流的题目较少，但可以通过经典问题“LeetCode 1514. 概率最大的路径”理解增广路思想（该题是求最大概率路径，可用 Dijkstra 解决）。这里我们以 LeetCode 1462. 课程表 IV 为例，它本质是传递闭包问题，也可以用最大流思想建模（但非标准流），此处仅作引子。实际可去 POJ 1273 练习标准最大流。
2️⃣ Edmonds-Karp 算法（BFS 版）
🎯 一句话记住
用 BFS 找最短增广路，保证多项式时间复杂度。
🤔 核心思想
Edmonds-Karp 是 Ford-Fulkerson 的一种具体实现，使用 BFS 寻找增广路径，保证每次找到的增广路径是边数最少的。时间复杂度为 O(VE2)O(VE2)，适用于中小规模图。
📊 流程图
💻 代码实现
/**
* Edmonds-Karp 算法（BFS）
*/
function edmondsKarp(n, graph, s, t) {
const residual = graph.map(row => [...row]);
const parent = new Array(n).fill(-1);
let maxFlow = 0;
const bfs = () => {
parent.fill(-1);
parent[s] = s;
const queue = [s];
while (queue.length) {
const u = queue.shift();
for (let v = 0; v < n; v++) {
if (parent[v] === -1 && residual[u][v] > 0) {
parent[v] = u;
if (v === t) return true;
queue.push(v);
}
}
}
return false;
};
while (bfs()) {
let pathFlow = Infinity;
for (let v = t; v !== s; v = parent[v]) {
const u = parent[v];
pathFlow = Math.min(pathFlow, residual[u][v]);
}
for (let v = t; v !== s; v = parent[v]) {
const u = parent[v];
residual[u][v] -= pathFlow;
residual[v][u] += pathFlow;
}
maxFlow += pathFlow;
}
return maxFlow;
}🏆 LeetCode 例题
同上，LeetCode 上无直接 Edmonds-Karp 题目，但可结合“LeetCode 1514. 概率最大的路径”练习 BFS 思想。
3️⃣ Dinic 算法（最常用）
🎯 一句话记住
BFS 建分层图，DFS 多路增广，效率高。
🤔 核心思想
Dinic 算法是目前最常用的最大流算法。它先通过 BFS 建立分层图（level graph），然后利用 DFS 进行多路增广（一次 DFS 可找出多条增广路），直到分层图中无法到达汇点。时间复杂度 O(EV)O(EV) 对于单位容量图，一般图 O(V2E)O(V2E)，实际非常快。
📊 流程图
-
VisuAlgo 演示（选择 Dinic 算法）
💻 代码实现
/**
* Dinic 算法（邻接表实现）
*/
class Dinic {
constructor(n) {
this.n = n;
this.graph = Array.from({ length: n }, () => []);
}
addEdge(u, v, cap) {
this.graph[u].push({ to: v, rev: this.graph[v].length, cap });
this.graph[v].push({ to: u, rev: this.graph[u].length - 1, cap: 0 });
}
bfs(s, t) {
this.level = new Array(this.n).fill(-1);
const queue = [s];
this.level[s] = 0;
while (queue.length) {
const u = queue.shift();
for (const e of this.graph[u]) {
if (e.cap > 0 && this.level[e.to] < 0) {
this.level[e.to] = this.level[u] + 1;
queue.push(e.to);
}
}
}
return this.level[t] >= 0;
}
dfs(u, t, f) {
if (u === t) return f;
for (let i = this.it[u]; i < this.graph[u].length; i++) {
const e = this.graph[u][i];
if (e.cap > 0 && this.level[u] < this.level[e.to]) {
const d = this.dfs(e.to, t, Math.min(f, e.cap));
if (d > 0) {
e.cap -= d;
this.graph[e.to][e.rev].cap += d;
return d;
}
}
this.it[u]++;
}
return 0;
}
maxFlow(s, t) {
let flow = 0;
while (this.bfs(s, t)) {
this.it = new Array(this.n).fill(0);
let f;
while ((f = this.dfs(s, t, Infinity)) > 0) {
flow += f;
}
}
return flow;
}
}🏆 LeetCode 例题
同上，无直接题目。但我们可以将 LeetCode 1595. 连通两组点的最小成本 转化为最小费用最大流问题（KM 算法），此处先介绍 Dinic，后续 KM 算法会用到类似思想。
三、最小割与最大流最小割定理
🎯 一句话记住
网络的最大流等于最小割的容量，割掉这些边就断了源汇。
🤔 核心思想
割是将顶点集划分为两个不相交集合 SS 和 TT，其中 s∈S,t∈Ts∈S,t∈T。割的容量是从 SS 到 TT 的所有边的容量之和。最大流最小割定理指出：最大流的值等于所有割中最小的容量。这一定理是许多图论问题（如二分图最大匹配、图像分割）的理论基础。
📊 流程图
最大流最小割定理动态演示（选择 “Min Cut” 模式）
💻 代码实现（在最大流基础上获取最小割
// 在 Dinic 执行完 maxFlow 后，level 数组中 level[v] !== -1 的点构成 S 集合
function minCut(dinic, s, t) {
dinic.maxFlow(s, t);
const S = [];
for (let i = 0; i < dinic.n; i++) {
if (dinic.level[i] !== -1) S.push(i);
}
// S 到 T 的边即为最小割边
return S;
}🏆 LeetCode 例题
LeetCode 2101. 引爆最多的炸弹 可转化为最小割模型，但代码较长。我们选用 LeetCode 1462. 课程表 IV 作为最小割思想的引例：求所有可达关系（传递闭包）本质上等价于求最小割的补集（连通性）。实际可考虑 LeetCode 1514 的变形。
四、二分图匹配
1️⃣ 匈牙利算法（求最大匹配）
🎯 一句话记住
为左边每个点找对象，找不到就尝试让已匹配的换人，直到无法增广。
🤔 核心思想
匈牙利算法用于求解二分图最大匹配问题。它通过不断寻找增广路（交错路径）来扩大匹配。算法核心是 DFS 尝试为每个左部点匹配，如果当前右部点已被匹配，则递归尝试让该右部点的原配重新找其他点，直到找到增广路或失败。时间复杂度 O(VE)O(VE)。
💻 代码实现
/**
* 匈牙利算法（邻接表）
* @param {number} n 左部节点数
* @param {number} m 右部节点数
* @param {number[][]} edges 边集 [u, v] (0-based)
* @returns {number} 最大匹配数
*/
function hungarian(n, m, edges) {
const graph = Array.from({ length: n }, () => []);
for (const [u, v] of edges) graph[u].push(v);
const matchR = new Array(m).fill(-1); // 右部匹配的左部节点
let result = 0;
const dfs = (u, visited) => {
for (const v of graph[u]) {
if (!visited[v]) {
visited[v] = true;
if (matchR[v] === -1 || dfs(matchR[v], visited)) {
matchR[v] = u;
return true;
}
}
}
return false;
};
for (let u = 0; u < n; u++) {
const visited = new Array(m).fill(false);
if (dfs(u, visited)) result++;
}
return result;
}🏆 LeetCode 例题
LeetCode 886. 可能的二分法 是二分图判定（染色法），但匈牙利算法可用于最大匹配。LeetCode 上有一道经典匹配题：LeetCode 1792. 最大平均通过率 不是匹配。这里我们以 LeetCode 1066. 校园自行车分配 II 为例，它可以用状态压缩 DP 或最小权匹配（KM）求解，也是二分图匹配问题。
2️⃣ KM 算法（求最大/最小权完美匹配）
🎯 一句话记住
每个点带顶标，通过调整顶标找相等子图的完美匹配。
🤔 核心思想
KM 算法（Kuhn-Munkres）用于求解带权二分图的最大权完美匹配。它给每个左部点和右部点分配一个顶标（标杆），保持 lx[u]+ly[v]≥w[u][v]lx[u]+ly[v]≥w[u][v]，然后在相等子图（满足 lx[u]+ly[v]=w[u][v]lx[u]+ly[v]=w[u][v] 的边）中寻找增广路。如果找不到，调整顶标降低上界，继续寻找。时间复杂度 O(n3)O(n3)。
💻 代码实现（最大权完美匹配）
/**
* KM 算法（最大权完美匹配）
* @param {number} n 顶点数（左=右=n）
* @param {number[][]} w 权重矩阵，w[i][j] 表示左i与右j的边权
* @returns {number} 最大权值和
*/
function km(n, w) {
const lx = new Array(n).fill(-Infinity);
const ly = new Array(n).fill(0);
const match = new Array(n).fill(-1);
const slack = new Array(n);
const visX = new Array(n);
const visY = new Array(n);
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
lx[i] = Math.max(lx[i], w[i][j]);
}
}
const dfs = (x) => {
visX[x] = true;
for (let y = 0; y < n; y++) {
if (visY[y]) continue;
const gap = lx[x] + ly[y] - w[x][y];
if (gap === 0) {
visY[y] = true;
if (match[y] === -1 || dfs(match[y])) {
match[y] = x;
return true;
}
} else {
slack[y] = Math.min(slack[y], gap);
}
}
return false;
};
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) slack[j] = Infinity;
while (true) {
visX.fill(false);
visY.fill(false);
if (dfs(i)) break;
let delta = Infinity;
for (let j = 0; j < n; j++) {
if (!visY[j]) delta = Math.min(delta, slack[j]);
}
for (let j = 0; j < n; j++) {
if (visX[j]) lx[j] -= delta;
if (visY[j]) ly[j] += delta;
else slack[j] -= delta;
}
}
}
let ans = 0;
for (let i = 0; i < n; i++) {
if (match[i] !== -1) ans += w[match[i]][i];
}
return ans;
}🏆 LeetCode 例题
LeetCode 1595. 连通两组点的最小成本 是二分图最小权匹配的典型应用，可以直接使用 KM 算法求解（将权重取负转化为最大权匹配）
var connectTwoGroups = function(cost) {
const n = cost.length;
const m = cost[0].length;
// 将问题转化为最小权匹配（右部可能多出点，需虚拟点处理）
// 此处简化实现，使用状态压缩 DP 更直观
// 实际可用 KM 算法，但需处理 n 和 m 不等的情况
// 这里展示状态压缩 DP 解法
const minCost = new Array(1 << m).fill(Infinity);
minCost[0] = 0;
for (let i = 0; i < n; i++) {
const newMinCost = new Array(1 << m).fill(Infinity);
for (let mask = 0; mask < (1 << m); mask++) {
if (minCost[mask] === Infinity) continue;
for (let j = 0; j < m; j++) {
const newMask = mask | (1 << j);
newMinCost[newMask] = Math.min(newMinCost[newMask], minCost[mask] + cost[i][j]);
}
}
// 右部点可重复匹配（因为可以连接多个左部点），需额外处理
// 此处简化，实际需要更复杂的 DP
}
// 完整解法略，具体可参考官方题解
return 0;
};五、网络流与二分图匹配对比
| 算法 | 类型 | 时间复杂度 | 适用场景 |
|---|---|---|---|
| Ford-Fulkerson | 最大流 | O(E × maxFlow) | 理论框架 |
| Edmonds-Karp | 最大流 | O(VE²) | 小规模 |
| Dinic | 最大流 | O(V²E) 实际快 | 通用 |
| 匈牙利 | 二分图最大匹配 | O(VE) | 无权匹配 |
| KM | 二分图最优匹配 | O(V³) | 带权完美匹配 |
📌 面试常见问题
-
最大流最小割定理的直观理解？
-
割的容量是切断源汇所需付出的最小代价，最大流就是能送达的最大流量，两者相等。
-
-
Dinic 为什么比 Edmonds-Karp 快？
-
Dinic 通过 BFS 分层 + DFS 多路增广，一次 DFS 可找出多条增广路，减少了 BFS 次数。
-
-
匈牙利算法中增广路的本质？
-
从未匹配的左部点出发，经过未匹配边、匹配边、未匹配边……最终到达一个未匹配的右部点，这样反转路径上的匹配状态就能增加一对匹配。
-
-
KM 算法中顶标调整的物理意义？
-
顶标表示当前每个点愿意付出的最大代价，调整顶标相当于降低期望，允许更差的边进入相等子图，从而找到增广路。
-
🎯 下期预告
下一期我们将进入动态规划的世界，从线性 DP 到树形 DP，从背包问题到状态压缩，用递推思维解决最优化问题！
如果你觉得这篇文章对你有帮助，欢迎点赞、收藏、转发！
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
23
0- 0
已为社区贡献3条内容
所有评论(0)