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

匈牙利算法（Hungarian Algorithm）是求解二分图最大匹配问题的经典算法，由匈牙利数学家Edmonds于1965年提出。该算法基于增广路（Augmenting Path）思想，通过不断寻找可增广路径来增加匹配数，直到不存在增广路为止。二分图最大匹配在任务分配、资源调度、婚姻匹配和推荐系统等领域有着广泛应用。本文将用Java实现匈牙利算法的DFS和BFS两种版本，并讲解KM算法（Kuhn-Munkres）的带权扩展。

核心概念

二分图：顶点集可划分为两个不相交子集X和Y，且每条边的两个端点分别属于X和Y。

匹配：边集M ⊆ E，其中任意两条边没有公共顶点。

最大匹配：包含边数最多的匹配。

增广路：从一个未匹配点出发，交替经过非匹配边和匹配边，最终到达另一个未匹配点的路径。增广路的一个重要性质是：将增广路上的匹配边与非匹配边互换，匹配数会增加1。

匈牙利算法核心定理：一个匹配是最大匹配，当且仅当不存在增广路。

DFS版本实现

import java.util.*;

/**
 * 匈牙利算法 - DFS版本
 * 求解二分图最大匹配
 * 时间复杂度: O(VE)
 * 适合稀疏图
 */
public class HungarianAlgorithmDFS {

    private int nLeft;           // 左部顶点数
    private int nRight;          // 右部顶点数
    private List<Integer>[] graph; // 邻接表，graph[u]表示左部顶点u的所有邻接右部顶点
    private int[] matchRight;    // matchRight[v] = 与右部顶点v匹配的左部顶点
    private boolean[] visited;   // DFS访问标记

    @SuppressWarnings("unchecked")
    public HungarianAlgorithmDFS(int nLeft, int nRight) {
        this.nLeft = nLeft;
        this.nRight = nRight;
        graph = new ArrayList[nLeft];
        for (int i = 0; i < nLeft; i++) {
            graph[i] = new ArrayList<>();
        }
        matchRight = new int[nRight];
        Arrays.fill(matchRight, -1);
    }

    /**
     * 添加边（从左部u到右部v）
     */
    public void addEdge(int u, int v) {
        graph[u].add(v);
    }

    /**
     * 寻找增广路
     * @param u 当前左部顶点
     * @return 是否找到增广路
     */
    private boolean findAugmentingPath(int u) {
        for (int v : graph[u]) {
            if (visited[v]) continue;
            visited[v] = true;

            // 如果v未匹配，或v的匹配点可以找到新的匹配
            if (matchRight[v] == -1 || findAugmentingPath(matchRight[v])) {
                matchRight[v] = u;
                return true;
            }
        }
        return false;
    }

    /**
     * 执行匈牙利算法，返回最大匹配数
     */
    public int maxMatching() {
        int matchCount = 0;

        for (int u = 0; u < nLeft; u++) {
            visited = new boolean[nRight];
            if (findAugmentingPath(u)) {
                matchCount++;
            }
        }

        return matchCount;
    }

    /**
     * 获取匹配结果
     * @return 左部顶点到右部顶点的匹配映射
     */
    public int[] getMatching() {
        int[] matchLeft = new int[nLeft];
        Arrays.fill(matchLeft, -1);
        for (int v = 0; v < nRight; v++) {
            if (matchRight[v] != -1) {
                matchLeft[matchRight[v]] = v;
            }
        }
        return matchLeft;
    }

    /**
     * 打印匹配结果
     */
    public void printMatching() {
        int[] matchLeft = getMatching();
        System.out.println("=== 最大匹配结果 ===");
        for (int u = 0; u < nLeft; u++) {
            if (matchLeft[u] != -1) {
                System.out.println("左部" + u + " <-> 右部" + matchLeft[u]);
            }
        }
        System.out.println("最大匹配数: " + maxMatching());
    }
}

BFS版本实现（Hopcroft-Karp思想）

import java.util.*;

/**
 * 匈牙利算法 - BFS版本（Hopcroft-Karp优化思想）
 * 通过分层BFS一次性找多条增广路
 * 时间复杂度: O(E * sqrt(V))
 */
public class HungarianAlgorithmBFS {

    private int nLeft, nRight;
    private List<Integer>[] graph;
    private int[] matchLeft;   // 左部匹配
    private int[] matchRight;  // 右部匹配
    private int[] dist;        // BFS分层距离
    private final int NIL = 0; // 虚拟空节点（1-based索引时使用）

    @SuppressWarnings("unchecked")
    public HungarianAlgorithmBFS(int nLeft, int nRight) {
        this.nLeft = nLeft;
        this.nRight = nRight;
        graph = new ArrayList[nLeft + 1];
        for (int i = 0; i <= nLeft; i++) {
            graph[i] = new ArrayList<>();
        }
        matchLeft = new int[nLeft + 1];
        matchRight = new int[nRight + 1];
        dist = new int[nLeft + 1];
    }

    public void addEdge(int u, int v) {
        graph[u].add(v);
    }

    /**
     * BFS构建分层图
     */
    private boolean bfs() {
        Queue<Integer> queue = new LinkedList<>();

        for (int u = 1; u <= nLeft; u++) {
            if (matchLeft[u] == 0) {
                dist[u] = 0;
                queue.offer(u);
            } else {
                dist[u] = Integer.MAX_VALUE;
            }
        }

        dist[0] = Integer.MAX_VALUE; // NIL节点

        while (!queue.isEmpty()) {
            int u = queue.poll();
            if (dist[u] < dist[0]) {
                for (int v : graph[u]) {
                    if (dist[matchRight[v]] == Integer.MAX_VALUE) {
                        dist[matchRight[v]] = dist[u] + 1;
                        queue.offer(matchRight[v]);
                    }
                }
            }
        }

        return dist[0] != Integer.MAX_VALUE;
    }

    /**
     * DFS在分层图上寻找增广路
     */
    private boolean dfs(int u) {
        if (u != 0) {
            for (int v : graph[u]) {
                if (dist[matchRight[v]] == dist[u] + 1 && dfs(matchRight[v])) {
                    matchLeft[u] = v;
                    matchRight[v] = u;
                    return true;
                }
            }
            dist[u] = Integer.MAX_VALUE;
            return false;
        }
        return true;
    }

    public int maxMatching() {
        int matching = 0;
        while (bfs()) {
            for (int u = 1; u <= nLeft; u++) {
                if (matchLeft[u] == 0 && dfs(u)) {
                    matching++;
                }
            }
        }
        return matching;
    }
}

任务分配应用示例

/**
 * 工作任务分配场景演示
 * 将n个任务分配给m个员工，每个员工只能做特定任务
 */
public class TaskAssignmentDemo {

    public static void main(String[] args) {
        // 5个任务，5个员工
        int tasks = 5;
        int workers = 5;

        HungarianAlgorithmDFS hungarian = new HungarianAlgorithmDFS(tasks, workers);

        // 员工能做的任务（员工0-4，任务0-4）
        // 员工0: 任务0, 1, 2
        hungarian.addEdge(0, 0);
        hungarian.addEdge(0, 1);
        hungarian.addEdge(0, 2);

        // 员工1: 任务1, 2, 3
        hungarian.addEdge(1, 1);
        hungarian.addEdge(1, 2);
        hungarian.addEdge(1, 3);

        // 员工2: 任务2, 3, 4
        hungarian.addEdge(2, 2);
        hungarian.addEdge(2, 3);
        hungarian.addEdge(2, 4);

        // 员工3: 任务0, 3
        hungarian.addEdge(3, 0);
        hungarian.addEdge(3, 3);

        // 员工4: 任务1, 4
        hungarian.addEdge(4, 1);
        hungarian.addEdge(4, 4);

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

复杂度分析

实现	时间复杂度	空间复杂度	适用场景
DFS匈牙利	O(VE)	O(V + E)	稀疏图，实现简单
BFS匈牙利(HK)	O(E√V)	O(V + E)	大规模图，效率更高
KM算法	O(V³)或O(VE)	O(V²)	带权最大匹配

KM算法简介（带权扩展）

当二分图的边带有权重时，需要求最大权匹配。KM算法通过维护顶标（Vertex Label）和相等子图来解决：

顶标：为每个顶点分配一个数值，满足对于任意边(u,v)，有label[u] + label[v] ≥ weight[u][v]
相等子图：只保留满足label[u] + label[v] = weight[u][v]的边构成的子图
算法流程：在相等子图中寻找完美匹配，若找不到则调整顶标，扩大相等子图

KM算法的时间复杂度为O(V³)，使用松弛量优化后可降至O(VE)。

扩展应用

稳定婚姻问题：Gale-Shapley算法，确保没有 blocking pair
最小顶点覆盖：Kőnig定理指出，二分图最小顶点覆盖等于最大匹配
最大独立集：等于顶点数减去最小顶点覆盖（对于二分图）
Dilworth定理：偏序集的最小链划分等于最大反链长度

Tagged with: Java 二分图二分图匹配任务分配匈牙利算法图论最大匹配