C语言实现匈牙利算法：从二分图匹配到数学建模实战

1. 项目概述：从数学建模到代码实现

最近在辅导几个学生准备数学建模竞赛，发现很多队伍在处理任务分配、资源调度这类优化问题时，第一反应是去套用复杂的智能算法，结果往往代码冗长、调试困难，最后效果还不一定好。其实，很多这类“最优匹配”问题，用经典的匈牙利算法就能优雅高效地解决。它就像是解决“谁该做什么”这类问题的“瑞士军刀”，思路清晰，实现也不复杂。

这个项目，我们就来亲手用C语言实现匈牙利算法，解决经典的二分图最大匹配问题。你可能会问，为什么是C语言？在数学建模中，尤其是涉及到底层算法实现、追求极致效率，或者需要在嵌入式等资源受限环境中运行时，C语言的优势就凸显出来了。它没有高级语言那些花哨的语法糖，迫使你去理解算法的每一个内存操作和逻辑步骤，这种理解对于深刻掌握算法精髓至关重要。而且，一个用C写好的、经过优化的核心算法模块，可以非常方便地被MATLAB、Python等建模常用语言调用，作为性能关键部分的补充。

我们将从二分图匹配这个实际问题场景出发，一步步推导匈牙利算法的核心思想，然后将其转化为清晰的C语言代码。不止于写出能跑的代码，我更会分享如何设计数据结构来提升效率、调试中会遇到哪些“坑”，以及如何将这个小程序扩展成一个实用的算法模块。无论你是正在备战数学建模、学习算法数据结构，还是单纯对如何将精妙数学思想落地成代码感兴趣，这篇内容都能给你带来可直接复用的干货。

2. 匈牙利算法的核心思想与建模场景解析

2.1 二分图匹配：问题从何而来？

在我们开始敲代码之前，必须先把问题本身和算法的思路吃透。匈牙利算法解决的是“二分图最大匹配”问题。听起来有点学术，但其实场景非常普遍。

想象一下数学建模竞赛中的几个经典问题：

• 2016年国赛A题“系泊系统的设计”：虽然主要涉及力学优化，但在多目标、多参数的方案择优过程中，本质上也是在寻找“最优搭配”。
• 任务分配问题：有若干项任务和若干台机器（或人员），每台机器处理不同任务的时间或成本不同。如何分配使得总耗时最短或成本最低？这可以转化为一个加权二分图匹配问题，匈牙利算法是其基础。
• 资源调度问题：比如“云资源分配”、“出租车与乘客的匹配”，都是典型的二分图模型。一边是资源供给方，一边是需求方，我们需要在满足一定约束下，实现最大数量的成功匹配或最优整体效益。

什么是二分图？简单说，你可以把所有对象分成两个集合，比如集合U（左部）和集合V（右部）。我们只关心从U到V之间的连接关系。一个“匹配”就是一组边的集合，其中任意两条边没有公共顶点。就像你不能把同一个任务同时分给两个人，也不能让一个人同时干两件事。“最大匹配”就是找到边数最多的这样一个集合。

匈牙利算法的聪明之处在于，它不采用暴力搜索，而是通过一种“腾挪”的策略，不断寻找增广路径来增加匹配数。增广路径是理解这个算法的钥匙：这是一条起点和终点都是未匹配点，路径上匹配边和非匹配边交替出现的路径。找到这样一条路径后，我们把路径上所有边的状态反转（匹配的变成不匹配，不匹配的变成匹配），匹配的总边数就能恰好增加一条。算法就是反复寻找增广路径，直到找不到为止，此时就得到了最大匹配。

2.2 匈牙利算法的步骤拆解与直观理解

让我们把上述思想具体化为可操作的步骤。假设我们有一个用邻接矩阵表示的二分图，u_num和v_num分别是左右两部分的顶点数。

1. 初始化：所有顶点均标记为未匹配。
2. 循环尝试：对于左部集合U中的每一个顶点u，我们都尝试为它寻找一个匹配。
3. 深度优先搜索（DFS）寻找增广路：这是核心函数。为当前左顶点u寻找匹配时，需要遍历所有右顶点v。
   • 如果v未被当前本轮搜索访问过，且u与v之间有边相连，则标记v为已访问。
   • 接着检查v：如果v还未被匹配，或者我们能为v当前匹配的左顶点match_v[v]找到一个新的匹配（这里递归调用DFS），那么我们就成功找到了增广路。此时，将u与v匹配，并返回成功。
4. 结果统计：如果对某个u，DFS返回成功，则总匹配数加一。

这个过程可以形象地理解为“牵线搭桥”。当你想为左部的A先生找对象（右部）时，你先看他心仪列表里的B小姐。如果B小姐单身，那就直接牵手成功。如果B小姐已经和C先生在一起了，那你不能硬抢，而是要去问问C先生：“你能不能换一个对象？” 这就变成了一个递归问题：为C先生寻找新的对象（除了B小姐）。如果C先生找到了D小姐（单身），那么C先生就和D小姐在一起，B小姐就空出来可以和A先生在一起了。通过这种“协商”与“腾挪”，最终可能让更多人配对成功。

注意：经典的匈牙利算法时间复杂度是O(U*V)，对于稠密图（边很多）效率很高。在建模中，当问题规模（顶点数）在几百到几千时，直接用这个实现通常就够了。如果规模更大，可能需要考虑更优化的Hopcroft-Karp算法（O(sqrt(V)*E)），但实现也复杂不少。

3. C语言实现：数据结构设计与代码精讲

理解了算法思想，接下来就是如何用C语言这把“手术刀”将其精准实现。C语言实现算法的魅力在于，你需要自己管理一切，这让你对算法的内存访问和流程控制有前所未有的掌控感。

3.1 数据结构的选择：为什么是邻接矩阵？

存储图，我们主要有邻接矩阵和邻接表两种方式。这里我强烈推荐使用邻接矩阵，尤其对于数学建模中常见的、规模不是特别巨大的二分图匹配问题。

• 直观对应模型：很多建模问题天然地给出一个代价矩阵或关联矩阵（比如任务-人员的完成时间矩阵），这本身就是一个邻接矩阵（或可轻易转化为0-1邻接矩阵）。直接使用它，省去了转换的步骤。
• 访问速度快：判断两点间是否有边，只需要O(1)的时间，这对于DFS中频繁的边存在性检查非常有利。
• 实现简单：代码更简洁，易于调试。对于初学者或追求快速实现原型来说，这是最佳选择。

当然，如果图非常稀疏（边数远小于顶点数的平方），邻接表可以节省大量空间。但在建模竞赛的有限时间内，邻接矩阵的稳定性和简便性往往优先级更高。

我们的数据结构设计如下：

#define MAX_N 105 // 根据问题规模预估的最大顶点数，可调整 int u_num, v_num; // 左部顶点数，右部顶点数 int graph[MAX_N][MAX_N]; // 邻接矩阵，graph[u][v]=1表示有边 int match_v[MAX_N]; // 记录右部顶点v当前匹配的左部顶点编号，-1表示未匹配 int visited[MAX_N]; // 在每一轮DFS中，标记右部顶点是否被访问过

match_v数组是核心，它记录了当前匹配的状态。visited数组在每次为左部顶点u寻找增广路时都需要重新初始化，它保证了DFS不会陷入循环。

3.2 核心函数：DFS寻找增广路

这是算法的灵魂所在。我们将它封装成一个独立的函数。

// 尝试为左部顶点u寻找增广路 int dfs(int u) { for (int v = 0; v < v_num; ++v) { // 条件1: u和v之间有边 条件2: 本轮搜索中v还未被访问 if (graph[u][v] && !visited[v]) { visited[v] = 1; // 立即标记访问，防止重复递归 // 情况1: v未匹配，可直接匹配 // 情况2: v已匹配，尝试让其“原配”match_v[v]去找新的匹配 if (match_v[v] == -1 || dfs(match_v[v])) { match_v[v] = u; // 匹配成功，更新关系 return 1; } } } return 0; // 尝试了所有v，都找不到增广路 }

关键点解析：

1. visited[v] = 1;的位置：在判断graph[u][v]成立后立即标记。这一点至关重要！它防止了在后续递归dfs(match_v[v])时，又回头尝试访问v，导致无限递归。
2. 递归调用dfs(match_v[v])：这正体现了“腾挪”的思想。它问的是：“v现在的对象match_v[v]，你能不能换个对象？” 如果这个递归调用返回成功，就意味着腾挪成功，v就可以空出来给u了。
3. 返回值：返回1表示找到增广路，0表示未找到。

3.3 主函数框架与匹配流程

主函数负责遍历所有左部顶点，并调用DFS尝试增广。

int hungarian() { int match_count = 0; // 初始化匹配状态为-1（未匹配） memset(match_v, -1, sizeof(match_v)); for (int u = 0; u < u_num; ++u) { // 每一轮尝试前，清空右部的访问标记 memset(visited, 0, sizeof(visited)); // 如果为u找到增广路，总匹配数加一 if (dfs(u)) { match_count++; } } return match_count; // 返回最大匹配数 }

流程清晰：对每个左顶点u，都给它一次全新的寻找机会（清空visited）。只要dfs(u)成功，就意味着通过可能的“腾挪”，成功将u纳入匹配，匹配总数增加。

3.4 从0-1匹配到带权匹配：KM算法引子

我们上面实现的是无权图（或0-1图）的最大匹配。但在数学建模中，更常见的是带权二分图最佳完美匹配，即著名的指派问题：每个人做不同工作的效率不同，如何分配使总效率最高？这需要用到Kuhn-Munkres算法（KM算法）。

KM算法是匈牙利算法的加权扩展，核心思想是引入“顶标”和“相等子图”的概念。它通过调整顶标的值，逐步构造出一个存在完美匹配的相等子图，而此匹配就是最优匹配。虽然实现比基础匈牙利算法复杂，但框架相似。如果你掌握了匈牙利算法的C实现，理解KM算法就打下了坚实基础。在代码上，你需要增加lx,ly两个数组存储顶标，slack数组辅助优化，修改DFS函数以在相等子图中寻找增广路，并增加顶标调整的逻辑。

实操心得：在数学建模中，如果遇到的是标准指派问题（人数等于任务数，求最小总成本或最大总收益），强烈建议直接使用MATLAB的assignproblem函数或LINGO等优化软件的内置求解器，它们稳定且高效。自己用C实现KM算法，更多是出于学习目的或嵌入特定定制化流程中。对于非标准问题（如人数任务数不等），可以将其转化为标准问题（补虚设的行或列，代价设为0或极大值），再调用标准解法。

4. 代码实现全貌与详细注释

下面给出一个完整的、可编译运行的C语言程序示例，它包含了一个简单的测试用例。我们将通过这个例子，展示如何将理论转化为实际代码。

#include <stdio.h> #include <string.h> #define MAX_N 105 int u_num, v_num; int graph[MAX_N][MAX_N]; int match_v[MAX_N]; int visited[MAX_N]; // DFS寻找增广路 int dfs(int u) { for (int v = 0; v < v_num; ++v) { // 关键：先判断是否有边且未访问，再标记访问 if (graph[u][v] && !visited[v]) { visited[v] = 1; // 立即标记，防止环路 // 如果v未匹配，或能为v的原配找到新对象 if (match_v[v] == -1 || dfs(match_v[v])) { match_v[v] = u; // 建立或更新匹配关系 return 1; // 找到增广路，成功 } } } return 0; // 尝试所有v均失败 } // 匈牙利算法主函数 int hungarian() { int match_count = 0; memset(match_v, -1, sizeof(match_v)); // 初始化为无匹配 for (int u = 0; u < u_num; ++u) { memset(visited, 0, sizeof(visited)); // 每轮尝试前清空访问标记 if (dfs(u)) { match_count++; } } return match_count; } // 打印匹配结果 void print_matching() { printf("最大匹配数为: %d\n", hungarian()); printf("具体的匹配对 (左部 -> 右部):\n"); for (int v = 0; v < v_num; ++v) { if (match_v[v] != -1) { printf(" %d -- %d\n", match_v[v], v); } } } int main() { // 示例：一个简单的二分图 // 左部顶点数4个 (0,1,2,3)，右部顶点数4个 (0,1,2,3) u_num = 4; v_num = 4; // 初始化邻接矩阵为0 memset(graph, 0, sizeof(graph)); // 手动设置边关系，模拟一个二分图 // 左0连接右1,右2 graph[0][1] = 1; graph[0][2] = 1; // 左1连接右0,右2 graph[1][0] = 1; graph[1][2] = 1; // 左2连接右1,右3 graph[2][1] = 1; graph[2][3] = 1; // 左3连接右2 graph[3][2] = 1; printf("二分图邻接矩阵 (左部为行，右部为列):\n"); for (int i = 0; i < u_num; ++i) { for (int j = 0; j < v_num; ++j) { printf("%d ", graph[i][j]); } printf("\n"); } printf("\n"); // 执行匈牙利算法并输出结果 print_matching(); return 0; }

代码要点与测试解析：

1. 图的构建：我们在main函数里手动初始化了一个4x4的二分图。在实际应用中，这部分应该替换为从文件读取或根据问题逻辑生成graph矩阵的代码。
2. 函数分工：hungarian()是主调度函数，dfs()是核心递归函数，print_matching()用于友好地输出结果。这种分工让代码结构清晰。
3. 测试结果：运行上述代码，你会得到类似以下的输出。最大匹配数应为3（例如：0-2, 1-0, 2-3）。这验证了算法在非完全二分图上也能找到最大匹配。

5. 深度优化、内存管理与错误排查

一个能跑通的代码只是起点，一个健壮、高效的代码才是目标。下面分享几个在实际编码和数学建模应用中的进阶要点。

5.1 性能优化与空间权衡

• 使用邻接表处理稀疏图：如果问题规模很大（比如顶点数>1000）且图非常稀疏，邻接矩阵的O(U*V)空间开销和初始化时间会成为瓶颈。此时应改用邻接表。

  // 简单的邻接表示例（使用动态数组或链表更佳） vector<int> adj[MAX_N]; // C++风格示意，C中需用链表或动态数组实现 // 添加边：adj[u].push_back(v); // DFS中遍历：for (int i = 0; i < adj[u].size(); ++i) { int v = adj[u][i]; ... }

  在C中实现动态邻接表稍复杂，可以使用“链式前向星”结构，既能节省空间，遍历效率也高。这在ACM竞赛代码中很常见，数学建模中若对性能有极致要求可考虑。

• visited数组的优化：我们每轮DFS都使用memset清空整个visited数组，这是O(V)的操作。一个常见的优化技巧是使用一个“时间戳”变量vis_id和一个vis数组。每次DFS开始时，vis_id++。判断是否访问过改为判断vis[v] == vis_id，标记访问改为vis[v] = vis_id。这样就避免了全局清空，将O(V)的清空操作降为O(1)的整数比较。

5.2 内存管理：静态数组与动态分配

示例中使用了静态数组MAX_N。这在竞赛或已知问题上限时很方便。但在更通用的工具函数中，或者问题规模未知时，动态内存分配更安全。

int **graph; int *match_v, *visited; // 初始化函数 void init(int u_size, int v_size) { u_num = u_size; v_num = v_size; graph = (int**)malloc(u_num * sizeof(int*)); for(int i=0; i<u_num; i++) graph[i] = (int*)calloc(v_num, sizeof(int)); // 使用calloc初始化为0 match_v = (int*)malloc(v_num * sizeof(int)); visited = (int*)malloc(v_num * sizeof(int)); // ... 其他初始化 } // 使用完毕后务必记得 free

切记：动态分配内存后，一定要在程序结束时或函数返回前正确释放，避免内存泄漏。在数学建模的一次性脚本中这可能不是大问题，但养成好习惯很重要。

5.3 常见错误与调试技巧实录

即使算法思路清晰，实现时也难免踩坑。下面是我和学生们常遇到的几个问题：

1. 无限递归或栈溢出：

   • 原因：最可能是在DFS中忘记标记visited[v]=1，或者标记的位置不对（比如放在了递归调用之后），导致在递归中重复访问同一个顶点，形成环路。
   • 排查：在小规模测试用例上，打印每次DFS进入和离开的顶点u和尝试的顶点v，观察访问序列。确保visited标记逻辑正确。

2. 匹配结果错误（匹配数偏少）：

   • 原因A：邻接矩阵graph构建错误。比如误以为是无向图而对称赋值（匈牙利算法处理的是有向的二分图，从U到V），或者数据读取出错。
   • 验证：首先打印出graph矩阵，确认边的关系符合预期。
   • 原因B：match_v数组初始化或更新错误。确保初始化全为-1，且只在dfs返回1时才更新match_v[v] = u。
   • 调试：在dfs函数中成功匹配时，打印一条日志，如printf(“Match: %d -> %d\n”, u, v);，跟踪匹配的形成过程。

3. 数组越界：

   • 原因：顶点编号从1开始，但代码按从0开始处理，导致访问graph[u-1][v-1]时忘记减1，或者循环边界< u_num错写成<= u_num。
   • 预防：统一约定。我强烈建议内部处理一律使用0-based索引。如果输入数据是1-based，在读入时立即转换为0-based。这能减少大量低级错误。

4. 多组数据输入未重置：

   • 场景：数学建模中可能需要用同一程序处理多个测试案例。
   • 错误：处理完一组数据后，没有重置match_v,graph等全局或静态变量，导致下一组数据计算结果错误。
   • 解决：将核心算法封装进函数，并将图数据、匹配数组等作为参数传入。或者在处理每组新数据前，显式地调用memset进行重置。

独家避坑技巧：在编写DFS递归函数时，在函数入口处加一个深度打印，对于调试复杂递归逻辑非常有帮助。

int dfs(int u, int depth) { // 打印缩进，直观显示递归深度 for(int i=0; i<depth; i++) printf(" "); printf("dfs(u=%d)\n", u); // ... 函数体 }

调用时传入初始深度0。这能帮你一眼看清递归的调用栈，快速定位死循环或逻辑错误。

6. 从算法模块到建模应用实战

最后，我们来聊聊如何把这个C语言实现的匈牙利算法“小模块”，融入到实际的数学建模解题流程中。它不应该只是一个孤立的程序。

6.1 模型构建：识别问题中的二分图结构

这是应用算法的第一步，也是最关键的一步。拿到一个建模问题，如何抽象？

1. 识别两个互补集合：寻找问题中天然成对出现的两类实体。如：工作 vs 工人、订单 vs 配送车、实验样本 vs 检测设备、广告位 vs 广告商。
2. 定义“匹配”的含义：明确怎样的分配是可行的、有效的。这决定了邻接矩阵graph[i][j]的值是0/1（能否匹配），还是一个权重（匹配的效益或成本）。
3. 确定优化目标：是最大化匹配数量（如最多完成的任务数），还是最大化总效益/最小化总成本？前者用最大匹配，后者用最佳完美匹配（KM算法）。

举例：2024年高教社杯国赛C题通常涉及资源调度或路径优化。假设其中一问是“在某个时间段内，如何将有限的救援队伍最优地派往多个受灾点？” 我们可以将“救援队伍”视为左部U，“受灾点”视为右部V。graph[u][v]=1表示队伍u具备前往受灾点v的能力（考虑距离、专业匹配等）。目标可能是“派出尽可能多的队伍”（最大匹配），也可能是“最小化总响应时间”（加权匹配，权重为时间）。

6.2 数据接口：C代码与建模环境的协同

在建模中，主流程可能在MATLAB或Python中。C语言实现的算法可以作为高性能计算内核。

• 方案一：编译成独立可执行文件

  • 将C程序编译成.exe（Windows）或可执行文件（Linux/Mac）。
  • 在MATLAB中使用system命令调用，如system(‘hungarian.exe input.txt output.txt’)。
  • 在Python中使用subprocess模块调用。
  • 数据交换：通过文本文件。主程序将邻接矩阵写入input.txt，C程序读取、计算，将匹配结果写入output.txt，主程序再读回。
  • 优点：简单，跨语言通用。
  • 缺点：文件IO有开销，不适合频繁调用。

• 方案二：编译成共享库（DLL/SO）

  • 将C函数（如int hungarian(int** graph, int u, int v, int* match_result)）编译成动态链接库。
  • MATLAB可以直接加载并调用C共享库函数（loadlibrary,calllib）。
  • Python可以通过ctypes模块直接调用。
  • 优点：调用效率高，无文件IO开销，数据通过内存直接传递。
  • 缺点：配置稍复杂，需要处理不同平台下的编译和链接问题。

对于数学建模竞赛，如果算法只调用几次，方案一的简单可靠性更具优势。如果算法需要在一个大循环中调用成千上万次（例如在蒙特卡洛模拟中），那么方案二的性能收益将是决定性的。

6.3 结果验证与可视化

算法跑出结果后，不能直接相信。必须验证。

• 逻辑验证：检查匹配结果是否满足“一对一”的约束。遍历match_v数组，确保没有两个右顶点匹配到同一个左顶点（在算法正确实现下不会发生，但可作为检查）。
• 手动验算：对于小规模样例，手动推导最大匹配，与程序结果对比。
• 交叉验证：用另一种方法验证。例如，对于最大匹配问题，可以用线性规划（LP）在MATLAB中建模求解（0-1整数规划），对比结果是否一致。对于小规模问题，甚至可以用暴力枚举来验证。
• 可视化：如果顶点数不多，可以画图。用MATLAB的plot或gplot函数，将二分图的两部分顶点画在两列，用线条连接原图的边，再用高亮颜色标出算法找到的匹配边。直观的可视化能立刻发现匹配是否合理、是否还有改进空间。

将匈牙利算法的C实现融入数学建模，其价值不仅在于解决了一个子问题，更在于你掌握了一种将复杂算法高效工程化的能力。这种能力让你在面临其他需要自定义高效算法的场景时，能够从容地设计、实现、调试和集成，从而在竞赛或实际项目中构建出更强大、更灵活的解决方案。