1. 算法概述

匈牙利算法（Hungarian Algorithm）是一种用于求解二分图最大匹配的组合优化算法。给定一个二分图（顶点集可划分为左右两部分，所有边都连接左右两侧），匈牙利算法能够在线性时间内找到最大数量的匹配边，使得没有两条边共享同一个顶点。

注意：此处介绍的匈牙利算法是二分图匹配版本（Kuhn-Munkres 算法的简化版），用于求解无权二分图的最大匹配，而非带权二分图的最优匹配（KM 算法）。

2. 核心思想

匈牙利算法的核心是增广路（Augmenting Path） 理论：

  • 增广路：一条从未匹配点出发，交替经过"非匹配边 → 匹配边 → 非匹配边 → …"，最终到达另一个未匹配点的路径。
  • 关键性质：对一条增广路进行"取反"操作（将路径上的匹配边变为非匹配边，非匹配边变为匹配边），匹配数 +1。
  • 算法流程：依次尝试为每一个左侧顶点寻找增广路。若能找到，则匹配数 +1；否则该顶点无法匹配。
  • DFS 实现：递归地在右侧寻找可匹配的顶点，利用 matchR 数组记录右侧顶点的匹配对象。

增广路示意图

增广前:  L1 --- R1 (已匹配)
         L2        R2 (未匹配)
         L2 --- R1 (尝试匹配，发现R1已被占)
         回溯L1：L1 --- R2 (找到替代)
增广后:  L1 --- R2
         L2 --- R1
匹配数从 1 增加到 2

3. 算法步骤/伪代码

Hungarian(L_size, R_size, graph):
    matchR[R_size] = -1   // 右侧顶点匹配的左顶点，-1 表示未匹配
    
    for each left vertex u in [0, L_size):
        visited[R_size] = false
        if dfs(u): match_count++

    return match_count

function dfs(u):
    for each right vertex v in graph[u]:
        if visited[v]: continue
        visited[v] = true
        // 如果 v 未匹配，或者 v 的匹配对象能找到其他匹配
        if matchR[v] == -1 or dfs(matchR[v]):
            matchR[v] = u
            return true
    return false

4. C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

// ==================== 匈牙利算法 (DFS 增广路) ====================
class Hungarian {
private:
    int L; // 左侧顶点数
    int R; // 右侧顶点数
    vector<vector<int>> graph; // 邻接表，只存左侧到右侧的边
    vector<int> matchR;        // matchR[v] = u 表示右侧v匹配了左侧u，-1未匹配
    vector<bool> visited;      // 每次 DFS 的访问标记

    bool dfs(int u) {
        for (int v : graph[u]) {
            if (visited[v]) continue;
            visited[v] = true;
            // 如果 v 未匹配，或者 v 的当前匹配者能找到新的匹配
            if (matchR[v] == -1 || dfs(matchR[v])) {
                matchR[v] = u;
                return true;
            }
        }
        return false;
    }

public:
    Hungarian(int leftSize, int rightSize)
        : L(leftSize), R(rightSize), graph(leftSize),
          matchR(rightSize, -1), visited(rightSize, false) {}

    void addEdge(int left, int right) {
        graph[left].push_back(right);
    }

    int maxMatch() {
        int result = 0;
        for (int u = 0; u < L; u++) {
            // 每次 DFS 前清空 visited
            fill(visited.begin(), visited.end(), false);
            if (dfs(u)) {
                result++;
            }
        }
        return result;
    }

    // 获取匹配结果
    vector<pair<int, int>> getMatches() {
        vector<pair<int, int>> matches;
        for (int v = 0; v < R; v++) {
            if (matchR[v] != -1) {
                matches.push_back({matchR[v], v});
            }
        }
        return matches;
    }
};

// ==================== 测试 ====================
int main() {
    // 构造二分图
    // 左侧 4 个顶点 (0,1,2,3)，右侧 4 个顶点 (0,1,2,3)
    // L0 -> R0, R1
    // L1 -> R0, R2
    // L2 -> R1, R2, R3
    // L3 -> R3
    Hungarian hungarian(4, 4);
    hungarian.addEdge(0, 0);
    hungarian.addEdge(0, 1);
    hungarian.addEdge(1, 0);
    hungarian.addEdge(1, 2);
    hungarian.addEdge(2, 1);
    hungarian.addEdge(2, 2);
    hungarian.addEdge(2, 3);
    hungarian.addEdge(3, 3);

    int maxMatch = hungarian.maxMatch();
    cout << "最大匹配数: " << maxMatch << endl;
    // 期望输出: 4 (可以完美匹配)

    auto matches = hungarian.getMatches();
    cout << "匹配结果 (左->右):" << endl;
    for (auto& [l, r] : matches) {
        cout << "  L" << l << " -> R" << r << endl;
    }

    // ============ 示例2: 任务分配问题 ============
    // 3 个工人，4 个任务，每个工人只能做特定任务
    // W0 能做 T0, T1
    // W1 能做 T1, T2
    // W2 能做 T2, T3
    Hungarian taskAssignment(3, 4);
    taskAssignment.addEdge(0, 0);
    taskAssignment.addEdge(0, 1);
    taskAssignment.addEdge(1, 1);
    taskAssignment.addEdge(1, 2);
    taskAssignment.addEdge(2, 2);
    taskAssignment.addEdge(2, 3);

    cout << "\n任务分配最大匹配数: " << taskAssignment.maxMatch() << endl;
    // 期望输出: 3

    auto taskMatches = taskAssignment.getMatches();
    cout << "任务分配结果:" << endl;
    for (auto& [w, t] : taskMatches) {
        cout << "  工人" << w << " -> 任务" << t << endl;
    }

    return 0;
}

运行示例

最大匹配数: 4
匹配结果 (左->右):
  L0 -> R1
  L1 -> R0
  L2 -> R2
  L3 -> R3

任务分配最大匹配数: 3
任务分配结果:
  工人0 -> 任务0
  工人1 -> 任务1
  工人2 -> 任务2

5. 复杂度分析

  • 时间复杂度：O(V × E)，其中 V 为左侧顶点数，E 为边数。
    • 对每个左侧顶点（O(V)），执行一次 DFS 尝试寻找增广路，每次 DFS 最坏 O(E)。
    • 实际运行中通常远小于此上界，因为 visited 数组会剪枝。
  • 空间复杂度：O(V + E)，存储邻接表、matchR 数组和 visited 数组。

若使用 BFS 实现（Hopcroft–Karp 算法），可将复杂度优化到 O(E√V)。

实现方式 时间复杂度 适用场景
DFS 匈牙利 O(VE) 中小规模图
Hopcroft–Karp O(E√V) 大规模稀疏图
Dinic 网络流 建模为最大流后求解

6. 应用场景

场景 说明
任务分配 将 N 个任务分配给 M 个工人，求最大可完成任务数
婚配问题 稳定婚姻问题的基础（男-女最大匹配）
课程-教室安排 课程与可用教室/时间段的匹配
棋盘覆盖 多米诺骨牌覆盖棋盘的最大放置数
机器人路径规划 多机器人到多目标点的最优分配
推荐系统 用户与物品（广告）的匹配

7. 经典例题

二分图最大匹配模板题（洛谷 P3386）

题目描述：给定一个二分图，左侧 n 个点，右侧 m 个点，e 条边。求最大匹配数。

解题思路：直接套用匈牙利算法模板。注意顶点编号通常从 1 开始，实现时做偏移处理。

输入格式：n m e，然后 e 行每行 u v 表示左侧 u 到右侧 v 的边。

关键代码要点：

  1. 左侧顶点依次尝试寻找增广路。
  2. visited 数组每次 DFS 前清零（避免重复访问）。
  3. matchR[v] 记录右侧 v 匹配的左顶点。
  4. 递归核心：if (matchR[v] == -1 || dfs(matchR[v]))。

扩展：带权二分图最优匹配

如果每条边有权重，需要求总权重最大的完美匹配，则需使用 KM 算法（Kuhn-Munkres） 或费用流求解，匈牙利算法仅适用于无权最大匹配。

  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 14ms
  4. Powered by Hydro v5.0.1 Community