数据结构与算法 / 系统课时

二分图最大匹配

二分图最大匹配

二分图最大匹配要在不共享端点的前提下选择尽可能多的边。把它转换为单位容量最大流后,增广、冲突消解和最优性证明都可以复用网络流框架,同时还能从最终流量中恢复每一对匹配关系。

学习目标

  • 将二分图系统化地转换为源点到汇点的流网络。
  • 理解整数流为何与合法匹配一一对应。
  • 编写程序求最大匹配数并恢复具体匹配边。

建模方法

设二分图左右顶点集合分别为 LL 与 RR。新增源点 ss 和汇点 tt,按以下规则建图:

  1. 从 ss 向每个左侧顶点连容量为 1 的边。
  2. 对每条二分图边 (u,v)(u,v),从左侧顶点 uu 向右侧顶点 vv 连容量为 1 的边。
  3. 从每个右侧顶点向 tt 连容量为 1 的边。

源点侧和汇点侧的单位容量保证每个顶点最多参与一次匹配。由于所有容量都是整数,增广算法得到的最大流也是整数流;中间层流量为 1 的边正好构成匹配。

二分图最大匹配到最大流的建模与恢复

核心原理

1. 匹配可以转换为可行流

若选中一条匹配边 (u,v)(u,v),就在路径 s→u→v→ts \to u \to v \to t 上发送 1 单位流。匹配边不共享端点,所以不会违反源点侧或汇点侧的容量限制,因此任意大小为 kk 的匹配都能产生值为 kk 的可行流。

2. 整数流可以恢复为匹配

反过来,单位容量网络中的整数流在每条边上只能取 0 或 1。对所有左侧到右侧、流量为 1 的边进行收集,就得到一组不共享端点的匹配边。于是最大流与最大匹配在规模上相等。

3. 复杂度

若直接使用 Edmonds-Karp,建图后的顶点数为 ∣L∣+∣R∣+2|L|+|R|+2,边数与候选匹配边数量同阶,最坏时间复杂度为 O(VE2)O(VE^2)。更大规模的二分图通常使用 Hopcroft-Karp,将复杂度降到 O(EV)O(E\sqrt{V});但最大流建模更通用,也便于继续扩展容量和附加约束。

完整可运行示例

下面的 Java 17 程序构造单位容量流网络,计算最大流,并检查原始中间层边是否承载 1 单位流来恢复匹配关系。

java
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]);
                }
            }
        }
    }
}

运行命令:

bash
javac BipartiteMatchingFlowDemo.java
java BipartiteMatchingFlowDemo

预期输出

text
最大匹配数: 3
匹配关系:
A - X
B - Z
C - Y

输出说明所有 3 个左侧顶点都被匹配,且每个右侧顶点只出现一次。具体匹配可能因增广路选择顺序而不同,但最大匹配数保持不变。

常见错误与练习

常见错误

建模时若把左侧到右侧的边设为大于 1 的容量,程序可能让同一候选关系承载多单位流,失去“选边”含义。普通最大匹配的三层边都应使用容量 1。

恢复匹配时不能仅检查原容量是否为 1,因为那只能说明候选边存在。应检查最终流量是否为 1;在本示例中等价于原容量为 1 且正向残量为 0。

练习

  1. 新增左侧顶点 D,候选边为 D - Z,扩展网络后验证最大匹配数是否变化,并解释瓶颈位于哪一侧顶点集合。
  2. 删除候选边 B - Z,运行程序并记录恢复出的匹配。验收条件是每个顶点最多出现一次,且程序输出的匹配数与实际列出的边数一致。

本课总结

  • 单位容量流网络把“不共享端点”的限制编码为容量约束。
  • 二分图匹配与整数流可以双向转换,因此最大匹配数等于最大流值。
  • 恢复匹配时,应读取左侧到右侧边上的最终流量,而不是只看候选边是否存在。

下一课预告

接下来可以继续学习更高效的二分图匹配算法,以及带权匹配、最小点覆盖和指派问题等建立在匹配结构之上的扩展模型。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

二分图最大匹配

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通