每日算法 — 使用java实现Hopcroft-Karp：二分图最大匹配的分层BFS优化

引言

二分图最大匹配是图论中的经典问题，在任务分配、资源调度、推荐系统等领域有广泛应用。匈牙利算法是基础的 O(VE) 解法，而 Hopcroft-Karp 算法通过分层 BFS + 多路 DFS 增广，将复杂度优化到 O(E√V)，是大规模二分图匹配的首选算法。

本文将用 Java 完整实现 Hopcroft-Karp 算法，讲解其分层思想、多路增广策略与复杂度证明。

问题建模

二分图

图 G = (U, V, E)，其中 U 和 V 是不相交的顶点集，E 中的边只连接 U 和 V 中的顶点。

匹配

边集 M ⊆ E，满足任意两条边不共享顶点。最大匹配是基数最大的匹配。

增广路

一条交替路径（匹配边/非匹配边交替），起点和终点都是未匹配点。沿增广路翻转匹配状态可使匹配数 +1。

核心思想

匈牙利算法的瓶颈

每次只找一条增广路，需要 O(E) 时间，最多 V 次增广，总复杂度 O(VE)。

Hopcroft-Karp 的优化

1. 分层 BFS：从所有未匹配的 U 顶点同时出发，构建到未匹配 V 顶点的最短增广路层次图
2. 多路 DFS 增广：在层次图上同时找出多条顶点不相交的最短增广路，一次性全部增广
3. 关键定理：每次增广后，最短增广路长度严格增加，因此最多 √V 轮即可收敛

完整 Java 实现

import java.util.*;

/**
 * Hopcroft-Karp 算法实现
 * 二分图最大匹配的分层BFS + 多路DFS优化
 * 时间复杂度: O(E * sqrt(V))
 */
public class HopcroftKarp {

    private final int nU; // U集合大小
    private final int nV; // V集合大小
    private final List<Integer>[] adj; // U到V的邻接表

    // 匹配数组: pairU[u]=v 表示U中u匹配到V中v
    private final int[] pairU;
    private final int[] pairV;
    // BFS层次距离
    private final int[] dist;

    // 无穷大标记
    private static final int INF = Integer.MAX_VALUE;

    /**
     * 构造函数
     * @param nU U集合顶点数 (0 ~ nU-1)
     * @param nV V集合顶点数 (0 ~ nV-1)
     */
    @SuppressWarnings("unchecked")
    public HopcroftKarp(int nU, int nV) {
        this.nU = nU;
        this.nV = nV;
        this.adj = new ArrayList[nU];
        for (int i = 0; i < nU; i++) {
            adj[i] = new ArrayList<>();
        }
        this.pairU = new int[nU];
        this.pairV = new int[nV];
        this.dist = new int[nU];
    }

    /**
     * 添加边 (u属于U, v属于V)
     */
    public void addEdge(int u, int v) {
        if (u < 0 || u >= nU || v < 0 || v >= nV) {
            throw new IllegalArgumentException("顶点越界");
        }
        adj[u].add(v);
    }

    /**
     * 主算法：返回最大匹配数
     */
    public int maxMatching() {
        // 初始化匹配数组
        Arrays.fill(pairU, -1);
        Arrays.fill(pairV, -1);

        int matching = 0;

        // 每轮BFS构建层次图，然后DFS多路增广
        while (bfs()) {
            // 对所有未匹配的U顶点尝试DFS增广
            for (int u = 0; u < nU; u++) {
                if (pairU[u] == -1) {
                    if (dfs(u)) {
                        matching++;
                    }
                }
            }
        }

        return matching;
    }

    /**
     * BFS构建层次图
     * 从所有未匹配的U顶点出发，计算到各U顶点的最短增广路距离
     * 返回是否存在增广路
     */
    private boolean bfs() {
        ArrayDeque<Integer> queue = new ArrayDeque<>();

        // 初始化：所有未匹配的U顶点距离为0，入队
        for (int u = 0; u < nU; u++) {
            if (pairU[u] == -1) {
                dist[u] = 0;
                queue.offer(u);
            } else {
                dist[u] = INF;
            }
        }

        // 设置一个虚拟目标的距离（用于标记是否存在增广路）
        // 实际上我们不需要显式NIL节点，只需检查是否能到达未匹配的V顶点
        boolean foundAugmentingPath = false;

        while (!queue.isEmpty()) {
            int u = queue.poll();

            // 只扩展最短增广路层次上的边
            for (int v : adj[u]) {
                int u2 = pairV[v]; // v的匹配点（如果已匹配）

                if (u2 != -1 && dist[u2] == INF) {
                    // v已匹配，沿匹配边走到对应的U顶点
                    dist[u2] = dist[u] + 1;
                    queue.offer(u2);
                } else if (u2 == -1) {
                    // v未匹配，找到增广路终点
                    foundAugmentingPath = true;
                }
            }
        }

        return foundAugmentingPath;
    }

    /**
     * DFS在层次图上寻找增广路
     * 只走最短增广路层次上的边，避免破坏其他增广路
     */
    private boolean dfs(int u) {
        for (int v : adj[u]) {
            int u2 = pairV[v];

            if (u2 == -1 || (dist[u2] == dist[u] + 1 && dfs(u2))) {
                // 找到增广路，更新匹配
                pairU[u] = v;
                pairV[v] = u;
                return true;
            }
        }

        // 无法从u出发找到增广路，标记为INF避免重复访问
        dist[u] = INF;
        return false;
    }

    /**
     * 获取匹配结果
     * @return 数组match[u]=v，若u未匹配则为-1
     */
    public int[] getMatching() {
        return pairU.clone();
    }

    /**
     * 打印匹配结果
     */
    public void printMatching() {
        System.out.println("最大匹配数: " + countMatching());
        System.out.println("匹配详情:");
        for (int u = 0; u < nU; u++) {
            if (pairU[u] != -1) {
                System.out.printf("  U%d ↔ V%d%n", u, pairU[u]);
            }
        }
    }

    /**
     * 统计匹配数
     */
    public int countMatching() {
        int count = 0;
        for (int v : pairU) {
            if (v != -1) count++;
        }
        return count;
    }

    /**
     * 验证匹配的正确性
     */
    public boolean verify() {
        Set<String> edges = new HashSet<>();
        for (int u = 0; u < nU; u++) {
            if (pairU[u] != -1) {
                // 检查是否是有效边
                if (!adj[u].contains(pairU[u])) return false;
                // 检查是否有冲突
                String key = pairU[u] + ""; // V顶点只能被匹配一次
                if (edges.contains(key)) return false;
                edges.add(key);
                // 检查双向一致性
                if (pairV[pairU[u]] != u) return false;
            }
        }
        return true;
    }

    /**
     * 构建测试用的随机二分图
     */
    public static HopcroftKarp randomBipartiteGraph(int nU, int nV, double edgeProb) {
        HopcroftKarp hk = new HopcroftKarp(nU, nV);
        Random rand = new Random(42);
        for (int u = 0; u < nU; u++) {
            for (int v = 0; v < nV; v++) {
                if (rand.nextDouble() < edgeProb) {
                    hk.addEdge(u, v);
                }
            }
        }
        return hk;
    }

    /**
     * 任务分配示例
     */
    public static void taskAssignmentDemo() {
        System.out.println("=== 任务分配示例 ===");
        // 5个工人，6个任务，每个工人能完成部分任务
        HopcroftKarp hk = new HopcroftKarp(5, 6);

        // 工人0可以完成任务0,1,2
        hk.addEdge(0, 0); hk.addEdge(0, 1); hk.addEdge(0, 2);
        // 工人1可以完成任务1,3
        hk.addEdge(1, 1); hk.addEdge(1, 3);
        // 工人2可以完成任务2,4,5
        hk.addEdge(2, 2); hk.addEdge(2, 4); hk.addEdge(2, 5);
        // 工人3可以完成任务0,3,5
        hk.addEdge(3, 0); hk.addEdge(3, 3); hk.addEdge(3, 5);
        // 工人4可以完成任务1,4
        hk.addEdge(4, 1); hk.addEdge(4, 4);

        int maxMatch = hk.maxMatching();
        System.out.println("最大可分配任务数: " + maxMatch);
        hk.printMatching();
    }

    /**
     * 与匈牙利算法（DFS版）的性能对比
     */
    public static void performanceComparison() {
        System.out.println("\n=== 性能对比 ===");
        int[] sizes = {100, 200, 500, 1000};

        for (int n : sizes) {
            HopcroftKarp hk = randomBipartiteGraph(n, n, 0.1);

            long start = System.nanoTime();
            int match = hk.maxMatching();
            long end = System.nanoTime();

            System.out.printf("n=%d, 匹配数=%d, 耗时=%.3fms%n",
                n, match, (end - start) / 1e6);
        }
    }

    /**
     * 测试完全二分图 K_{n,n}
     */
    public static void completeBipartiteTest(int n) {
        System.out.println("\n=== 完全二分图 K_" + n + "," + n + " ===");
        HopcroftKarp hk = new HopcroftKarp(n, n);
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
                hk.addEdge(u, v);
            }
        }

        long start = System.nanoTime();
        int match = hk.maxMatching();
        long end = System.nanoTime();

        System.out.println("最大匹配: " + match + " (期望: " + n + ")");
        System.out.println("验证: " + (hk.verify() ? "通过" : "失败"));
        System.out.printf("耗时: %.3fms%n", (end - start) / 1e6);
    }

    public static void main(String[] args) {
        taskAssignmentDemo();
        performanceComparison();
        completeBipartiteTest(500);
        completeBipartiteTest(2000);
    }
}

算法解析

为什么分层 BFS 有效

BFS 保证找到的是最短的增广路。关键定理：若最短增广路长度为 k，则一次多路增广后，新的最短增广路长度至少为 k+2。

为什么最多 √V 轮

• 设最大匹配为 M，|M| ≤ min(|U|, |V|)
• 前 √V 轮后，最短增广路长度 > √V
• 剩余未匹配点最多 |M|/√V 个（每条增广路需 √V 条边）
• 因此最多再 |M|/√V ≤ √V 轮
• 总轮数 O(√V)，每轮 O(E)，总复杂度 O(E√V)

多路增广的正确性

DFS 在层次图上只沿 dist[u2] == dist[u] + 1 的边前进，保证找到的都是同一最短长度的增广路，且顶点不相交（通过 dist[u] = INF 标记已访问）。

复杂度分析

扩展思考

1. 带权二分图匹配：使用匈牙利算法或最小费用最大流。
2. 一般图最大匹配：使用 Blossom 算法（Edmonds），复杂度 O(V³)。
3. 在线匹配：到达的顶点必须立即匹配，使用贪心或 Ranking 算法。

总结

Hopcroft-Karp 算法是二分图匹配的里程碑：通过分层 BFS 找到最短增广路集合，通过多路 DFS 一次性批量增广，将复杂度从 O(VE) 降至 O(E√V)。掌握其核心思想——按层次批量处理——对理解网络流、图匹配乃至并行算法设计都有深远启发。