数据结构与算法 / 系统课时
二分图最大匹配
二分图最大匹配
二分图最大匹配要在不共享端点的前提下选择尽可能多的边。把它转换为单位容量最大流后,增广、冲突消解和最优性证明都可以复用网络流框架,同时还能从最终流量中恢复每一对匹配关系。
学习目标
- 将二分图系统化地转换为源点到汇点的流网络。
- 理解整数流为何与合法匹配一一对应。
- 编写程序求最大匹配数并恢复具体匹配边。
建模方法
设二分图左右顶点集合分别为 与 。新增源点 和汇点 ,按以下规则建图:
- 从 向每个左侧顶点连容量为 1 的边。
- 对每条二分图边 ,从左侧顶点 向右侧顶点 连容量为 1 的边。
- 从每个右侧顶点向 连容量为 1 的边。
源点侧和汇点侧的单位容量保证每个顶点最多参与一次匹配。由于所有容量都是整数,增广算法得到的最大流也是整数流;中间层流量为 1 的边正好构成匹配。

核心原理
1. 匹配可以转换为可行流
若选中一条匹配边 ,就在路径 上发送 1 单位流。匹配边不共享端点,所以不会违反源点侧或汇点侧的容量限制,因此任意大小为 的匹配都能产生值为 的可行流。
2. 整数流可以恢复为匹配
反过来,单位容量网络中的整数流在每条边上只能取 0 或 1。对所有左侧到右侧、流量为 1 的边进行收集,就得到一组不共享端点的匹配边。于是最大流与最大匹配在规模上相等。
3. 复杂度
若直接使用 Edmonds-Karp,建图后的顶点数为 ,边数与候选匹配边数量同阶,最坏时间复杂度为 。更大规模的二分图通常使用 Hopcroft-Karp,将复杂度降到 ;但最大流建模更通用,也便于继续扩展容量和附加约束。
完整可运行示例
下面的 Java 17 程序构造单位容量流网络,计算最大流,并检查原始中间层边是否承载 1 单位流来恢复匹配关系。
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
public class BipartiteMatchingFlowDemo {
private static boolean bfs(int[][] residual, int source, int sink, int[] parent) {
Arrays.fill(parent, -1);
boolean[] visited = new boolean[residual.length];
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(source);
visited[source] = true;
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v = 0; v < residual.length; v++) {
if (!visited[v] && residual[u][v] > 0) {
parent[v] = u;
visited[v] = true;
if (v == sink) {
return true;
}
queue.offer(v);
}
}
}
return false;
}
private static int maxFlow(int[][] capacity, int source, int sink, int[][] residual) {
for (int i = 0; i < capacity.length; i++) {
residual[i] = Arrays.copyOf(capacity[i], capacity[i].length);
}
int[] parent = new int[capacity.length];
int totalFlow = 0;
// 单位容量网络中,每次增广都会新增一条匹配路径。
while (bfs(residual, source, sink, parent)) {
int pathFlow = Integer.MAX_VALUE;
for (int v = sink; v != source; v = parent[v]) {
pathFlow = Math.min(pathFlow, residual[parent[v]][v]);
}
for (int v = sink; v != source; v = parent[v]) {
int u = parent[v];
residual[u][v] -= pathFlow;
residual[v][u] += pathFlow;
}
totalFlow += pathFlow;
}
return totalFlow;
}
public static void main(String[] args) {
int source = 0;
int sink = 7;
int[][] capacity = new int[8][8];
String[] leftNames = {"A", "B", "C"};
String[] rightNames = {"X", "Y", "Z"};
// 顶点编号:左侧为 1..3,右侧为 4..6。
for (int left = 1; left <= 3; left++) {
capacity[source][left] = 1;
}
for (int right = 4; right <= 6; right++) {
capacity[right][sink] = 1;
}
capacity[1][4] = 1;
capacity[1][5] = 1;
capacity[2][4] = 1;
capacity[2][6] = 1;
capacity[3][5] = 1;
int[][] residual = new int[8][8];
int matchingSize = maxFlow(capacity, source, sink, residual);
System.out.println("最大匹配数: " + matchingSize);
System.out.println("匹配关系:");
// 原容量为 1 且正向残量变为 0,表示该边承载了 1 单位流。
for (int left = 1; left <= 3; left++) {
for (int right = 4; right <= 6; right++) {
if (capacity[left][right] == 1 && residual[left][right] == 0) {
System.out.println(leftNames[left - 1] + " - " + rightNames[right - 4]);
}
}
}
}
}运行命令:
javac BipartiteMatchingFlowDemo.java
java BipartiteMatchingFlowDemo预期输出
最大匹配数: 3
匹配关系:
A - X
B - Z
C - Y输出说明所有 3 个左侧顶点都被匹配,且每个右侧顶点只出现一次。具体匹配可能因增广路选择顺序而不同,但最大匹配数保持不变。
常见错误与练习
常见错误
建模时若把左侧到右侧的边设为大于 1 的容量,程序可能让同一候选关系承载多单位流,失去“选边”含义。普通最大匹配的三层边都应使用容量 1。
恢复匹配时不能仅检查原容量是否为 1,因为那只能说明候选边存在。应检查最终流量是否为 1;在本示例中等价于原容量为 1 且正向残量为 0。
练习
- 新增左侧顶点
D,候选边为D - Z,扩展网络后验证最大匹配数是否变化,并解释瓶颈位于哪一侧顶点集合。 - 删除候选边
B - Z,运行程序并记录恢复出的匹配。验收条件是每个顶点最多出现一次,且程序输出的匹配数与实际列出的边数一致。
本课总结
- 单位容量流网络把“不共享端点”的限制编码为容量约束。
- 二分图匹配与整数流可以双向转换,因此最大匹配数等于最大流值。
- 恢复匹配时,应读取左侧到右侧边上的最终流量,而不是只看候选边是否存在。
下一课预告
接下来可以继续学习更高效的二分图匹配算法,以及带权匹配、最小点覆盖和指派问题等建立在匹配结构之上的扩展模型。