匈牙利算法C++实现：从二分图匹配到实战应用

1. 项目概述从二分图匹配到匈牙利算法匈牙利算法这个名字听起来可能有点异域风情但它解决的是一个非常接地气的组合优化问题二分图最大匹配。我第一次接触它是在一个招聘系统的开发项目里当时的需求是根据候选人的技能标签和岗位的技能要求实现一个高效的智能人岗匹配推荐。这本质上就是一个典型的二分图匹配问题——候选人是一组顶点岗位是另一组顶点如果候选人的技能满足岗位要求就在他们之间连一条边。我们的目标就是为尽可能多的岗位找到最合适的候选人或者反过来。匈牙利算法就是解决这类问题的“瑞士军刀”。它由匈牙利数学家Dénes Kőnig和Jenő Egerváry在20世纪30年代提出核心思想是通过不断寻找增广路径来增加匹配数直到无法找到为止。这个过程听起来有点抽象但你可以把它想象成一个“月老牵线”的过程算法会尝试为左边的每个点比如候选人在右边找一个对象岗位如果心仪的对象已经被占了它不会轻易放弃而是会尝试让已经配对成功的“前任”们调整一下看看能不能腾出位置来。这种“协商调整”的机制正是匈牙利算法高效且优雅的地方。在C中实现匈牙利算法不仅是对图论和组合优化知识的实践更是对编程中DFS/BFS遍历、邻接表/矩阵使用、状态标记等基本功的一次综合考验。无论是参加算法竞赛如ACM/ICPC还是在实际的软件开发中如任务调度、资源分配、广告点击率预估中的匹配问题掌握一个清晰、高效的匈牙利算法实现都是非常有价值的。接下来我将以一个邻接表存储的二分图为例带你从零开始手把手实现一个经典的DFS版本匈牙利算法并深入探讨其性能优化和实战应用中的各种“坑”。2. 算法核心原理与C实现思路拆解在动手写代码之前我们必须把匈牙利算法的“灵魂”吃透。很多人实现出来后总觉得哪里不对劲或者效率不高往往是因为对原理的理解停留在表面。2.1 核心概念匹配、增广路径与交错路径首先明确几个关键术语。在一个二分图G(U, V, E)中U和V是互不相交的顶点集合E是连接它们的边。匹配一个边的集合M⊆E其中任意两条边都没有公共顶点。你可以理解为“成功配对”的集合。未匹配点在匹配M中没有被任何边关联到的顶点。交替路径一条路径其边在匹配M和非匹配边(E\M)之间交替出现。增广路径一条起点和终点都是未匹配点的交替路径。这是算法的核心。增广路径为什么重要因为如果我们找到一条增广路径就可以通过一个简单的操作——将路径上所有匹配边变为非匹配边所有非匹配边变为匹配边——来使得匹配的边数增加1。这个过程叫做“取反”。想象一下一条长度为奇数的路径两端未匹配内部边交替。取反后两端的点就被成功匹配进来了匹配总数自然1。匈牙利算法这里指用于二分图最大匹配的Kuhn-Munkres算法或简称KM算法的简化DFS形式的流程就是不断搜索增广路径并取反的过程伪代码如下初始化所有匹配为“空” 对于左边集合U中的每一个顶点u 清空右边集合V中所有顶点的“本次访问标记” 尝试为u寻找增广路径 如果找到则匹配数加1为单个点u寻找增广路径通常使用深度优先搜索。DFS函数bool dfs(u)的逻辑是遍历u所有邻接的右边顶点v。如果v未被访问过则标记访问。然后检查v如果v还未匹配或者能为v当前匹配的左顶点match[v]找到另一条增广路径即递归调用dfs(match[v])成功那么就把u和v配对成功即设置match[v] u并返回true。2.2 C实现方案选型邻接表 vs 邻接矩阵实现的第一步是选择数据结构来存储图。这直接影响了代码的复杂度和效率。邻接矩阵用一个二维数组g[u][v]表示左边点u和右边点v是否有边。查找u的邻接点需要遍历整个V集合。其优点是实现直观适用于稠密图边数接近|U||V|。但在稀疏图场景下O(|U||V|)的遍历开销是巨大的浪费。邻接表为每个左边顶点u维护一个链表或动态数组存储所有与之相连的右边顶点v。这是处理稀疏图的标准做法能显著减少不必要的遍历。在大多数实际问题中二分图往往是稀疏的一个候选人只适合少数岗位因此邻接表是我们的首选。在C中我们可以使用vectorvectorint来存储邻接表其中外层vector的索引对应左边顶点u内层vector存储其所有邻接的右边顶点v的编号。另一个关键设计是匹配关系的存储。我们通常用一个一维数组match[v]来记录右边顶点v当前匹配的是哪个左边顶点u。如果v未匹配则可以将其初始化为-1或0取决于顶点编号是否从0开始。同时在每次为新的u寻找增广路径时我们需要一个visited[v]数组来标记右边顶点v在本轮DFS中是否已被访问以防止在递归中陷入死循环。实操心得visited数组的清理时机有讲究。必须在为每个左边的u启动DFS之前对整个visited数组进行重置例如用memset或fill。如果将其放在DFS函数内部初始化或者在找到增广路径后不清除都会导致算法错误。这是新手最容易栽跟头的地方之一。3. 匈牙利算法C核心代码实现与逐行解析理论清晰后我们进入实战环节。下面我将呈现一个完整的、基于邻接表的DFS匈牙利算法实现并附上详细的注释和解析。3.1 数据结构定义与初始化#include iostream #include vector #include cstring // 用于memset using namespace std; class Hungarian { private: int n_left, n_right; // 左边顶点数右边顶点数 vectorvectorint adj; // 邻接表adj[u]存储u的所有邻接右顶点v vectorint match_right; // match_right[v] u, 表示右顶点v当前匹配的左顶点u-1表示未匹配 vectorbool visited; // visited[v] 标记右顶点v在本轮DFS中是否被访问过 public: // 构造函数初始化顶点数和数据结构 Hungarian(int left_num, int right_num) : n_left(left_num), n_right(right_num) { adj.resize(n_left); match_right.assign(n_right, -1); // 初始时所有右顶点未匹配 // visited数组会在每次dfs前动态重置大小并填充false避免反复分配 } // 添加一条从左顶点u到右顶点v的边 void addEdge(int u, int v) { // 通常假设顶点编号从0开始这里省略了边界检查 adj[u].push_back(v); }代码解析我们用一个类Hungarian来封装算法使代码更清晰、易于复用。n_left和n_right分别记录二分图两个集合的大小。adj是核心的邻接表类型为vectorvectorint。match_right数组大小为n_right索引是右顶点v值是与之匹配的左顶点u初始化为-1。visited数组在类内部声明但不在构造函数中固定大小。这是因为我们将在每次调用主函数maxMatch()时为每个左顶点u启动DFS前重新初始化这个数组。使用vectorbool并调用assign(n_right, false)比反复声明局部数组效率稍高且更安全。3.2 DFS增广路径搜索函数这是算法的灵魂所在也是最容易出错的部分。private: // DFS函数尝试为左顶点u寻找增广路径 bool dfs(int u) { // 遍历u的所有邻接右顶点 for (int v : adj[u]) { if (visited[v]) { continue; // 如果v在本轮已被访问过跳过 } visited[v] true; // 标记v为已访问 // 核心逻辑如果v未匹配或者能为v当前匹配的对象找到新的匹配 if (match_right[v] -1 || dfs(match_right[v])) { // 找到增广路进行匹配或重新匹配 match_right[v] u; return true; // 报告成功 } // 如果dfs(match_right[v])失败则继续尝试u的下一个邻接点 } // 遍历完所有邻接点都没找到增广路说明u暂时无法匹配 return false; }逐行解析与深度原理for (int v : adj[u])遍历左顶点u所有可能的匹配对象右顶点v。这里体现了邻接表的高效性只遍历实际存在的边。if (visited[v]) continue;visited数组是针对右顶点的。它的核心作用是防止在本轮为u寻找增广路径时重复尝试同一个右顶点v。为什么需要这个考虑一种情况左顶点u1尝试匹配v发现v已匹配u2于是递归尝试为u2找新的匹配。如果在为u2寻找时又通过其他边绕回来尝试匹配v就会形成循环导致无限递归。visited数组确保了每个右顶点v在本轮DFS中只被“考虑”一次。visited[v] true;一旦决定尝试v立即标记。这个标记在本次dfs(u)的整个递归过程中持续有效。if (match_right[v] -1 || dfs(match_right[v]))这是算法的精髓体现了“协商”思想。match_right[v] -1最简单的情况v还是“单身”直接撮合u和v。dfs(match_right[v])如果v已“名花有主”匹配了u2 match_right[v]算法不会放弃。它会尝试问u2“你能不能换个对象”。这个过程通过递归调用dfs(u2)来实现。如果dfs(u2)成功为u2找到了新的匹配对象比如v2那么u2就会“让出”v转而匹配v2。这样v就空出来了可以匹配当前的u。递归的成功会沿着调用链向上返回true。match_right[v] u;当上述条件满足时执行匹配操作。注意即使在递归情况下这个赋值也可能发生多次在递归返回的过程中最终保证增广路径上的所有匹配关系被正确“取反”。return true/false向上一层汇报本次寻找是否成功。3.3 主循环与最大匹配计算public: // 计算并返回最大匹配数 int maxMatch() { int matching 0; // 当前匹配数 for (int u 0; u n_left; u) { // 关键步骤为每个左顶点u启动DFS前重置visited数组 visited.assign(n_right, false); if (dfs(u)) { matching; } } return matching; } // 可选获取具体的匹配对用于输出结果 vectorpairint, int getMatchPairs() { vectorpairint, int pairs; for (int v 0; v n_right; v) { if (match_right[v] ! -1) { pairs.emplace_back(match_right[v], v); } } return pairs; } };主循环逻辑遍历每一个左顶点u。在尝试为u寻找增广路径之前必须清空visited数组。这是必须的因为每一轮DFS都是独立的尝试之前轮次的访问标记不能影响本轮。调用dfs(u)。如果成功意味着我们成功为u找到了匹配可能经过了一系列调整总匹配数matching加1。遍历完所有左顶点后matching就是最大匹配数。注意事项这个经典实现的时间复杂度是O(|U| * |E|)其中|E|是边数。因为最坏情况下每个左顶点u都要进行一次DFS而DFS可能会遍历所有边。对于顶点数较多几千以上的稠密图这个复杂度可能成为瓶颈。在实际工程中如果性能要求极高可以考虑BFS版本的匈牙利算法Hopcroft-Karp算法它能将复杂度降至O(sqrt(|V|) * |E|)但实现起来更复杂一些。4. 完整测试用例与实战场景模拟纸上得来终觉浅绝知此事要躬行。下面我们构建几个具体的测试用例从简单到复杂验证我们算法的正确性并模拟真实场景。4.1 基础测试一个小型二分图假设我们有3个求职者(U0, U1, U2)和3个岗位(V0, V1, V2)。匹配关系如下U0 能胜任 V0, V1U1 能胜任 V0, V2U2 只能胜任 V1int main() { // 测试用例1基础功能 Hungarian hungarian(3, 3); hungarian.addEdge(0, 0); hungarian.addEdge(0, 1); hungarian.addEdge(1, 0); hungarian.addEdge(1, 2); hungarian.addEdge(2, 1); int max_matching hungarian.maxMatch(); cout 最大匹配数: max_matching endl; auto pairs hungarian.getMatchPairs(); cout 匹配对详情: endl; for (auto p : pairs) { cout 左顶点 p.first - 右顶点 p.second endl; } // 预期输出 // 最大匹配数: 3 // 匹配对详情: // 左顶点 1 - 右顶点 0 // 左顶点 0 - 右顶点 1 // 左顶点 2 - 右顶点 2 // 注意匹配对的具体分配可能因DFS顺序不同而有差异但最大数一定是3。 return 0; }这个测试验证了算法在完全匹配Perfect Matching情况下的正确性。4.2 进阶测试模拟任务调度场景假设一个分布式系统有4个计算任务左顶点需要分配到3台服务器右顶点上执行每台服务器同时只能执行一个任务且任务对服务器有兼容性要求。任务0可在服务器0, 1上运行任务1只能在服务器0上运行任务2可在服务器1, 2上运行任务3可在服务器0, 2上运行显然服务器数少于任务数不可能全部匹配。void testTaskScheduling() { Hungarian scheduler(4, 3); // 4 tasks, 3 servers scheduler.addEdge(0, 0); scheduler.addEdge(0, 1); scheduler.addEdge(1, 0); scheduler.addEdge(2, 1); scheduler.addEdge(2, 2); scheduler.addEdge(3, 0); scheduler.addEdge(3, 2); int max_assigned scheduler.maxMatch(); cout 最多可分配的任务数: max_assigned endl; auto assignments scheduler.getMatchPairs(); cout 分配方案 (任务 - 服务器): endl; for (auto a : assignments) { cout Task a.first - Server a.second endl; } // 一种可能的输出 // 最多可分配的任务数: 3 // 分配方案 (任务 - 服务器): // Task 1 - Server 0 // Task 0 - Server 1 // Task 2 - Server 2 // 任务3没有被分配。 }这个例子展示了算法在非完全匹配场景下的应用并引出了一个实际问题当匹配数无法达到左顶点数时哪些顶点被“牺牲”了这取决于DFS遍历的顺序。在实际调度中我们可能需要对任务设置优先级这可以通过调整左顶点的处理顺序来实现。4.3 性能压测大规模稀疏图为了检验算法在实际中的性能我们可以生成一个大规模的随机二分图。例如左边5000个点右边5000个点每个左边点随机连接5-10个右边点。#include random void testLargeScale() { int left_num 5000, right_num 5000; Hungarian largeMatcher(left_num, right_num); std::random_device rd; std::mt19937 gen(rd()); std::uniform_int_distribution dis_right(0, right_num - 1); std::uniform_int_distribution dis_degree(5, 10); // 构建随机图 for (int u 0; u left_num; u) { int degree dis_degree(gen); // 简单去重确保添加的边不重复虽然对算法正确性非必须但更符合实际 unordered_setint connected; for (int d 0; d degree; d) { int v dis_right(gen); if (connected.insert(v).second) { // 如果成功插入即不重复 largeMatcher.addEdge(u, v); } } } auto start chrono::steady_clock::now(); int match_count largeMatcher.maxMatch(); auto end chrono::steady_clock::now(); auto duration chrono::duration_castchrono::milliseconds(end - start); cout 大规模图匹配完成。 endl; cout 左顶点数: left_num , 右顶点数: right_num endl; cout 最大匹配数: match_count endl; cout 计算耗时: duration.count() 毫秒 endl; }运行这个测试你可以直观感受到O(|U|*|E|)复杂度在稀疏图上的表现。在我的开发机上普通配置上述规模的计算通常在几百毫秒到一两秒内完成。如果时间过长就需要考虑优化比如使用更快的输入输出、改用Hopcroft-Karp算法或者对图进行预处理如删除孤立点。5. 常见问题排查与性能优化实战在实际编码和调试匈牙利算法时你会遇到一些典型问题。这里我总结了一份“避坑指南”。5.1 算法正确性相关陷阱问题1算法陷入死循环或递归深度过大。症状程序长时间不结束或直接栈溢出。根因与排查未正确设置或重置visited数组这是最常见的原因。确保visited数组在每次调用dfs(u)之前被完全重置为false。如果在dfs函数内部标记visited[v]true但在递归返回前没有回溯即设为false同时又在主循环中没有重置就会导致后续DFS无法访问某些点可能错过增广路但更危险的是在某些实现中可能导致无限递归。我们的实现采用了“每轮独立visited”的策略在主循环重置在递归中只标记不回溯这是正确且高效的。图存在自环或非二分性匈牙利算法严格适用于二分图。如果图中存在连接同一侧顶点的边或者图本身不是二分图存在奇环算法的行为是未定义的很可能死循环。在输入数据不可信时需要先进行二分图检测如染色法。解决方案严格按照3.2和3.3节的代码实现visited逻辑。对于数据确保输入是合法的二分图。问题2得到的匹配数明显小于预期。症状对于显然可以完全匹配的图算法只找到部分匹配。根因与排查顶点编号起始问题C中数组通常从0开始。如果你的输入数据顶点编号从1开始而代码按从0处理就会漏掉边或导致数组越界。仔细检查addEdge的参数和match_right数组的索引。邻接表构建错误确认添加的边是否正确。特别是在读取文件或处理复杂输入时容易出错。打印出邻接表的前几项进行核对。DFS递归中的状态污染如果错误地使用了全局或静态的visited数组并且没有妥善管理其生命周期会导致状态在不同轮次间污染。坚持使用成员变量并在每轮重置。解决方案编写一个小型单元测试使用4.1中的简单例子验证。使用调试器单步跟踪观察为某个特定左顶点u寻找匹配时dfs的递归调用过程以及match_right数组的变化。5.2 性能优化技巧当图的规模变大时原始的DFS匈牙利算法可能会变慢。以下是一些行之有效的优化手段优化1调整遍历顺序技巧在maxMatch()主循环中尝试对左顶点按照度邻接边数量进行升序排序后再进行匹配。直觉上优先匹配邻接点少的顶点可以减少后续调整的复杂度为邻接点多的顶点留下更多选择空间。代码示例int maxMatch() { vectorint left_vertices(n_left); iota(left_vertices.begin(), left_vertices.end(), 0); // 生成0,1,2,...序列 // 按度升序排序 sort(left_vertices.begin(), left_vertices.end(), [this](int a, int b) { return adj[a].size() adj[b].size(); }); int matching 0; for (int u : left_vertices) { // 按排序后的顺序遍历 visited.assign(n_right, false); if (dfs(u)) { matching; } } return matching; }效果对于结构不均匀的图此优化可能带来显著的加速有时可达10%-30%。但对于均匀随机图效果可能不明显。优化2使用迭代DFS或显式栈背景递归DFS虽然简洁但存在函数调用开销和栈深度限制。对于极深或极大规模的图可能引发栈溢出。方法用显式的stack数据结构模拟递归过程。这需要手动管理“回溯”状态代码会复杂不少但能避免递归深度限制。对于绝大多数竞赛和工程场景递归深度不超过左顶点数是足够的此优化非必需。优化3终极武器——Hopcroft-Karp算法何时使用当顶点数超过数千且图比较稠密时O(|U||E|)的复杂度可能成为瓶颈。Hopcroft-Karp算法通过使用BFS分层同时寻找多条最短增广路将复杂度降为O(sqrt(|V|)|E|)。实现复杂度显著高于DFS匈牙利。需要同时维护距离标号、使用BFS构建分层图、再用DFS或多路增广。除非性能是核心瓶颈否则DFS匈牙利因其实现简单而更具优势。5.3 内存与工程化考量内存布局对于超大规模图顶点数数十万以上使用vectorvectorint存储邻接表可能引发内存碎片问题。可以考虑使用“压缩邻接表”一个vectorint存储所有边的终点另一个vectorint存储每个顶点边的起始索引。这在图形学和高性能计算中很常见。多线程/并行化匈牙利算法本质上是顺序的因为每一步匹配都可能影响全局状态难以直接并行。一个思路是将二分图划分为多个子图分别求匹配后再合并处理边界但这非常复杂且容易得不偿失。输出匹配方案getMatchPairs()函数返回的是从右顶点视角的匹配。有时我们需要从左顶点视角查询。可以很容易地增加一个match_left数组在dfs成功匹配时同时更新match_left[u] v和match_right[v] u实现双向查询。6. 从算法到应用实战项目构思掌握了算法的实现我们来看看它能解决哪些实际问题。匈牙利算法不仅是算法题中的常客更是许多实际系统的基石。应用场景一在线广告匹配Ad Allocation这是互联网公司的核心问题之一。广告位右顶点需要和广告主左顶点进行匹配目标是最大化点击率或收入。边权重可以表示为预估点击率CTR或出价。基础的匈牙利算法解决的是最大基数匹配即匹配数最多。对于带权重的最大权匹配需要使用KM算法Kuhn-Munkres算法它是匈牙利算法的加权版本通过顶标和相等子图等概念来求解。应用场景二多目标跟踪Multiple Object Tracking在计算机视觉中需要将上一帧检测到的目标左顶点与当前帧检测到的目标右顶点关联起来。边的权重可以是目标之间的外观相似度如特征向量距离或运动预测的一致性如IOU重叠率。匈牙利算法可以快速找到最优的一对一关联保证一个目标最多只与一个目标匹配。应用场景三任务与资源调度正如我们测试用例所示将计算任务分配给服务器、将工人分配给工作站、将课程分配给教室等都是二分图匹配问题。约束条件如任务只能在某些服务器上运行体现在边的存在性上。如果需要考虑更复杂的约束如服务器有多个资源槽则可能转化为更复杂的图匹配或流问题。一个小型实战项目建议简易课程排课系统你可以尝试用匈牙利算法做一个简单的原型。将“课程节次”如周一第1节作为左顶点将“教室”作为右顶点。如果某节课可以在某个教室上则添加一条边。运行匈牙利算法可以得到一个最大化的课程-教室匹配方案。你可以在此基础上增加权重如优先安排大教室给大课尝试实现KM算法。从理解增广路径的巧妙到用C一行行实现递归DFS再到处理各种边界条件和性能优化匈牙利算法的实现之旅是一次对算法思想和工程实践能力的双重锻炼。它像一把钥匙打开了一类组合优化问题的大门。当你下次遇到“一对一匹配”需求时不妨先想想这能不能抽象成一个二分图如果能那么匈牙利算法很可能就是你高效、可靠的解决方案。记住清晰的visited数组管理和对递归“协商”过程的理解是写好这段代码的关键。多写、多调试、多思考不同数据下的表现你就能彻底驾驭这个经典的算法。