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

匈牙利算法的核心思想

匈牙利算法通过寻找“增广路径”（Augmenting Path）来逐步扩大匹配数量。增广路径是一条从未匹配点出发，交替经过非匹配边和匹配边，最终到达另一个未匹配点的路径。只要找到一条增广路径，就可以将匹配数加一。

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

C语言实现步骤

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

1. 定义数据结构

#define MAXN 100  // 最大节点数int graph[MAXN][MAXN];   // 邻接矩阵，graph[i][j] = 1 表示左部i与右部j有边int match[MAXN];         // match[j] = i 表示右部j被左部i匹配int visited[MAXN];       // 标记右部节点是否在当前DFS中被访问int n;                   // 左部和右部的节点数量（假设相等）

2. 寻找增广路径的函数

// 尝试为左部节点 u 找到一个匹配int dfs(int u) {    for (int v = 0; v < n; v++) {        if (graph[u][v] && !visited[v]) {            visited[v] = 1;            // 如果 v 未被匹配，或 v 的匹配对象能找到新匹配            if (match[v] == -1 || dfs(match[v])) {                match[v] = u;                return 1;            }        }    }    return 0;}

3. 主函数：计算最大匹配

int hungarian() {    int matching = 0;    memset(match, -1, sizeof(match));  // 初始化所有右部节点未匹配    for (int u = 0; u < n; u++) {        memset(visited, 0, sizeof(visited));  // 每次DFS前清空访问标记        if (dfs(u)) {            matching++;        }    }    return matching;}

4. 完整示例程序

#include <stdio.h>#include <string.h>#define MAXN 100int graph[MAXN][MAXN];int match[MAXN];int visited[MAXN];int n;int dfs(int u) {    for (int v = 0; v < n; v++) {        if (graph[u][v] && !visited[v]) {            visited[v] = 1;            if (match[v] == -1 || dfs(match[v])) {                match[v] = u;                return 1;            }        }    }    return 0;}int hungarian() {    int matching = 0;    memset(match, -1, sizeof(match));    for (int u = 0; u < n; u++) {        memset(visited, 0, sizeof(visited));        if (dfs(u)) matching++;    }    return matching;}int main() {    // 示例：3个工人，3个任务    n = 3;    // graph[i][j] = 1 表示工人i可以做任务j    graph[0][0] = graph[0][1] = 1;    graph[1][1] = graph[1][2] = 1;    graph[2][0] = graph[2][2] = 1;    int result = hungarian();    printf("最大匹配数（最多可分配的任务数）: %d\n", result);    // 输出具体匹配方案    for (int j = 0; j < n; j++) {        if (match[j] != -1) {            printf("工人 %d -> 任务 %d\n", match[j], j);        }    }    return 0;}

运行结果说明

上述程序输出：

最大匹配数（最多可分配的任务数）: 3工人 0 -> 任务 1工人 1 -> 任务 2工人 2 -> 任务 0

这表示所有3个工人都成功分配到了不同的任务，达到了最大匹配。

总结

通过本教程，你已经掌握了匈牙利算法的基本原理及其在C语言实现中的关键步骤。该算法是解决二分图最大匹配和任务分配问题的有力工具。

建议你动手敲一遍代码，修改输入数据，观察不同图结构下的匹配结果，加深理解。掌握这一算法，不仅能应对算法面试题，还能在实际项目中优化资源分配！