匈牙利算法详解（C++语言实现二分图最大匹配与任务分配问题）

什么是二分图最大匹配？

二分图（Bipartite Graph）是一种特殊的图，其顶点可以分为两个互不相交的集合 U 和 V，图中的每条边都连接 U 中的一个顶点和 V 中的一个顶点。

最大匹配是指在二分图中选择尽可能多的边，使得任意两条边都不共享同一个顶点。例如，有 3 个工人和 3 个任务，每个工人只能做某些任务，我们要找出最多能同时安排多少对“工人-任务”组合。

匈牙利算法的核心思想

匈牙利算法通过不断寻找增广路径（Augmenting Path）来扩大当前匹配。增广路径是一条从未匹配点出发，交替经过“非匹配边”和“匹配边”，最终到达另一个未匹配点的路径。一旦找到这样的路径，就可以将路径上的匹配状态“翻转”，从而增加匹配数量。

算法重复这一过程，直到找不到新的增广路径为止，此时的匹配即为最大匹配。

C++ 实现步骤

我们将使用邻接表表示二分图，并采用深度优先搜索（DFS）来寻找增广路径。

1. 定义数据结构

• graph：邻接表，graph[u] 表示左部点 u 可以连接的所有右部点。
• match：记录右部点被哪个左部点匹配，若未匹配则为 -1。
• used：在每次 DFS 中标记右部点是否已被访问，防止重复访问。

2. 核心函数：DFS 寻找增广路径

对于每个左部点 u，尝试为其找到一个匹配的右部点 v。如果 v 未被匹配，或者 v 的当前匹配点可以重新分配，则匹配成功。

3. 主循环：遍历所有左部点

对每个左部点调用 DFS，若成功找到增广路径，则最大匹配数加一。

完整 C++ 代码实现

#include <iostream>#include <vector>#include <cstring>using namespace std;// graph[u] 存储 u 能连接的所有右部点（从0开始编号）vector<vector<int>> graph;// match[v] 表示右部点 v 被哪个左部点匹配，-1 表示未匹配vector<int> match;// used[v] 标记在当前 DFS 中 v 是否被访问过vector<bool> used;bool dfs(int u) {    for (int v : graph[u]) {        if (!used[v]) {            used[v] = true;            // 如果 v 未匹配，或者 v 的匹配点可以重新分配            if (match[v] == -1 || dfs(match[v])) {                match[v] = u;                return true;            }        }    }    return false;}int hungarian(int n) {    // n 是左部点的数量    match.assign(graph.size(), -1); // 假设右部点数量不超过 graph.size()    int matching = 0;    for (int u = 0; u < n; ++u) {        used.assign(graph.size(), false);        if (dfs(u)) {            matching++;        }    }    return matching;}int main() {    // 示例：3个工人（左部），3个任务（右部）    int n = 3, m = 3;    graph.resize(n);    // 添加边：工人0可做任务0和1；工人1可做任务1；工人2可做任务1和2    graph[0] = {0, 1};    graph[1] = {1};    graph[2] = {1, 2};    int max_matching = hungarian(n);    cout << "最大匹配数为: " << max_matching << endl;    // 输出具体匹配方案    cout << "匹配方案:" << endl;    for (int v = 0; v < m; ++v) {        if (match[v] != -1) {            cout << "工人 " << match[v] << " → 任务 " << v << endl;        }    }    return 0;}

代码说明

• 我们假设左部点编号为 0 到 n-1，右部点编号为 0 到 m-1。
• graph 的大小应至少为 n（左部点数），每个元素是一个 vector，存储该左部点可连接的右部点。
• match 数组大小应至少为右部点数量，初始化为 -1。
• 每次调用 dfs(u) 前，必须重置 used 数组，确保本次搜索的独立性。

时间复杂度

该实现的时间复杂度为 O(n × m)，其中 n 是左部点数，m 是边数。对于稀疏图来说效率较高。

应用场景

匈牙利算法不仅用于理论研究，在实际工程中也有广泛应用，例如：

• 任务分配系统（如调度机器人执行任务）
• 求职者与岗位匹配
• 图像处理中的特征点匹配
• 资源分配优化

总结

通过本教程，你已经掌握了如何用 C++语言 实现 匈牙利算法 来解决 二分图最大匹配 问题。该算法是解决 任务分配问题 的有力工具，理解其原理和实现方式，将为你在算法竞赛或实际项目中打下坚实基础。

建议你动手运行上述代码，并尝试修改输入数据，观察输出结果的变化，加深理解！