每日算法 — 使用java实现二分图匹配：匈牙利算法与任务分配最优解

引言：从任务分配说起

想象你是一位项目经理，手中有 N 个开发任务和 N 名工程师。每名工程师只能负责自己擅长的部分任务，你的目标是把任务全部分配出去，且每名工程师恰好承担一项任务。这就是经典的二分图最大匹配问题——在左右两个集合之间寻找最多的”一对一”配对关系。

二分图匹配在现实生活中无处不在：婚恋网站的男女匹配、广告投放的用户定向、医院挂号的患者分诊、课程表的教师排课……本文将用 Java 完整实现经典的匈牙利算法（Hungarian Algorithm / Kuhn-Munkres），并以”任务分配”为场景，带你理解增广路、交替树等核心概念。

核心概念

二分图

二分图是指顶点可以划分为两个不相交集合 U 和 V 的图，且图中的每条边都连接 U 中的一个顶点与 V 中的一个顶点。形式化地说，图 G=(U,V,E) 满足 U∩V=∅，且 ∀(u,v)∈E 都有 u∈U, v∈V。

匹配

匹配 M 是边集 E 的一个子集，其中任意两条边都不共享顶点。如果 |M| = min(|U|,|V|)，则称该匹配为完美匹配。

增广路

对于当前匹配 M，一条增广路（Augmenting Path）是指从 U 中一个未匹配点出发，交替经过”非匹配边-匹配边-非匹配边…”，最终到达 V 中一个未匹配点的路径。增广路的关键性质是：将其上的匹配边与非匹配边互换，可以使匹配数增加 1。

匈牙利算法的核心思想就是：不断寻找增广路，直到不存在为止。

匈牙利算法（DFS 版本）详解

匈牙利算法有多种实现方式，其中最直观的是基于 DFS 的增广路搜索。算法流程如下：

1. 初始化匹配数组 match[v] = -1，表示 V 集合中每个顶点尚未匹配。
2. 遍历 U 集合中的每个顶点 u，尝试为其寻找匹配对象。
3. 对于当前顶点 u，遍历其所有邻接点 v。如果 v 未被访问过，则标记访问。
4. 如果 v 尚未匹配，或者 v 的匹配对象 match[v] 能够找到新的匹配（递归尝试），则将 u 与 v 匹配。
5. 重复步骤 2-4 直到所有 u 都尝试完毕。

该算法的时间复杂度为 O(|V|·|E|)，在稀疏图上表现良好。

Java 完整实现

下面的代码提供了一个完整的、可直接运行的 Java 程序。它包含图的数据结构、匈牙利算法核心逻辑，以及一个任务分配场景的完整示例。

import java.util.*;

/**
 * 二分图最大匹配 - 匈牙利算法（DFS版本）
 * 场景：任务分配问题
 */
public class BipartiteMatching {

    // U集合的大小（工程师数量）
    private int nU;
    // V集合的大小（任务数量）
    private int nV;
    // 邻接表：u -> [v1, v2, ...] 表示工程师u能胜任的任务列表
    private List<Integer>[] graph;
    // match[v] = u 表示任务v当前分配给工程师u，-1表示未分配
    private int[] match;
    // vis[v] 标记在本次DFS中任务v是否已被访问
    private boolean[] vis;

    public BipartiteMatching(int nU, int nV) {
        this.nU = nU;
        this.nV = nV;
        // 初始化邻接表
        graph = new ArrayList[nU + 1];
        for (int i = 1; i <= nU; i++) {
            graph[i] = new ArrayList<>();
        }
        match = new int[nV + 1];
        Arrays.fill(match, -1);
    }

    /**
     * 添加一条边：工程师u可以完成任务v
     */
    public void addEdge(int u, int v) {
        graph[u].add(v);
    }

    /**
     * 匈牙利算法核心：为工程师u寻找增广路
     * @param u 当前需要匹配的工程师
     * @return 是否成功为u找到匹配
     */
    private boolean dfs(int u) {
        // 遍历u能完成的所有任务
        for (int v : graph[u]) {
            // 如果本次DFS中v已经被访问过，跳过（避免死循环）
            if (vis[v]) continue;
            vis[v] = true;

            // 如果任务v尚未分配，或者当前占用v的工程师可以找到新的任务
            if (match[v] == -1 || dfs(match[v])) {
                match[v] = u; // 将任务v分配给工程师u
                return true;
            }
        }
        return false;
    }

    /**
     * 执行匈牙利算法，返回最大匹配数
     */
    public int hungarian() {
        int result = 0;
        // 依次为每个工程师尝试分配任务
        for (int u = 1; u <= nU; u++) {
            // 每次DFS前清空访问标记
            vis = new boolean[nV + 1];
            if (dfs(u)) {
                result++;
            }
        }
        return result;
    }

    /**
     * 获取最终的匹配结果
     * @return 匹配对列表，每对为 [工程师u, 任务v]
     */
    public List<int[]> getMatches() {
        List<int[]> pairs = new ArrayList<>();
        for (int v = 1; v <= nV; v++) {
            if (match[v] != -1) {
                pairs.add(new int[]{match[v], v});
            }
        }
        return pairs;
    }

    // ==================== 主程序与测试场景 ====================

    public static void main(String[] args) {
        // 场景：5名工程师，5个开发任务
        // 工程师编号：1-5，任务编号：1-5
        // 邻接关系表示每名工程师能胜任的任务
        int engineers = 5;
        int tasks = 5;

        BipartiteMatching bm = new BipartiteMatching(engineers, tasks);

        // 工程师1：可以完成任务1、任务2
        bm.addEdge(1, 1);
        bm.addEdge(1, 2);

        // 工程师2：可以完成任务2、任务3
        bm.addEdge(2, 2);
        bm.addEdge(2, 3);

        // 工程师3：可以完成任务1、任务4
        bm.addEdge(3, 1);
        bm.addEdge(3, 4);

        // 工程师4：可以完成任务3、任务5
        bm.addEdge(4, 3);
        bm.addEdge(4, 5);

        // 工程师5：可以完成任务4、任务5
        bm.addEdge(5, 4);
        bm.addEdge(5, 5);

        System.out.println("=== 任务分配场景 ===");
        System.out.println("工程师1: 任务1, 任务2");
        System.out.println("工程师2: 任务2, 任务3");
        System.out.println("工程师3: 任务1, 任务4");
        System.out.println("工程师4: 任务3, 任务5");
        System.out.println("工程师5: 任务4, 任务5");
        System.out.println();

        int maxMatch = bm.hungarian();
        System.out.println("最大匹配数: " + maxMatch);
        System.out.println();

        System.out.println("=== 最优分配方案 ===");
        List<int[]> pairs = bm.getMatches();
        for (int[] pair : pairs) {
            System.out.printf("工程师 %d -> 任务 %d%n", pair[0], pair[1]);
        }

        // 验证是否为完美匹配
        if (maxMatch == Math.min(engineers, tasks)) {
            System.out.println("\n达成完美匹配！所有任务均已分配。");
        } else {
            System.out.println("\n未能达成完美匹配，部分任务无人可接。");
        }
    }
}

代码运行结果

编译并运行上述程序，你将得到类似如下的输出：

=== 任务分配场景 ===
工程师1: 任务1, 任务2
工程师2: 任务2, 任务3
工程师3: 任务1, 任务4
工程师4: 任务3, 任务5
工程师5: 任务4, 任务5

最大匹配数: 5

=== 最优分配方案 ===
工程师 1 -> 任务 2
工程师 2 -> 任务 3
工程师 3 -> 任务 1
工程师 4 -> 任务 5
工程师 5 -> 任务 4

达成完美匹配！所有任务均已分配。

注意：由于 DFS 遍历邻接表的顺序不同，具体的分配方案可能有多种，但最大匹配数一定是 5。这体现了二分图最大匹配问题的特点——最优值唯一，最优解不唯一。

算法复杂度分析

对于稠密图，可考虑使用基于 BFS 的匈牙利算法（Hopcroft-Karp 算法），其时间复杂度可优化到 O(|E|·√|V|)。

扩展：从最大匹配到最大权匹配

上述实现解决的是”最大基数匹配”问题——只关心匹配数量最多。如果每个工程师完成不同任务的收益不同，问题就升级为最大权匹配。此时需要用到 KM（Kuhn-Munkres）算法，其核心思想是为每个顶点引入”顶标”，在相等子图上寻找完美匹配。当所有权重相等时，KM 算法退化为普通的匈牙利算法。

总结

匈牙利算法是图论中最优雅的经典算法之一。本文从任务分配这一贴近实际的场景切入，完整讲解了增广路、交替路径等核心概念，并提供了一份可直接编译运行的 Java 实现。理解这个算法后，你不仅能解决二分图匹配问题，还能为后续学习网络流、KM 算法、稳定婚姻问题等打下坚实基础。

思考题

1. 如果将场景改为”每名工程师最多承担两项任务”，算法需要如何改造？（提示：拆点法转化为标准二分图匹配）
2. 在上述代码基础上，如何输出所有不同的最大匹配方案？（提示：回溯枚举增广路的选择）