二分图匹配这个名词听起来像是纯理论课里的概念但只要你做过任务分配、课程排表、相亲平台推荐或者商家券派发这类需求多半已经在跟它打交道了。匈牙利算法作为求解二分图最大匹配的经典算法结构简单、代码量小却能让一堆看似无从下手的问题瞬间清晰起来。这篇文章我会从“为什么需要它”开始讲再手把手拆实现原理给出Java版本的完整代码最后聊聊怎么在Qt Creator工程里调起来用以及我在实际项目里踩过的几个坑。1. 二分图匹配是什么先搞清这几个概念1.1 二分图不是“两个图”很多初学者听到“二分图”第一反应是“是不是有两个图”其实完全不是一回事。二分图是图论里的一种特殊结构一张图的所有顶点可以被分成左右两个集合每条边的两个端点必须分别落在两个集合中集合内部不允许有任何边。用生活化的例子说把左侧想象成“需要被分配的任务”右侧想象成“能执行这些任务的人”。只有当某个任务能被某人完成时才存在一条从左到右的边。任务和任务之间不可能直接相连人和人之间也不可能直接相连这种天然的结构就是一个标准二分图。判断一个图是不是二分图其实有个很实用的方法就是看它能不能被两种颜色染色使得相邻顶点颜色不同。能染成就是二分图不能就不是。比如一个三角形三个顶点两两相连就无法做到相邻不同色所以它不可能是二分图。而一个正方形四个顶点组成环就可以左右交替着色即可。1.2 匹配、最大匹配、完美匹配别搞混在二分图中“匹配”指的是一组边满足任意两条边不共享同一个顶点。放到任务分配场景中匹配就是“每个任务最多分配给一个人每个人最多接手一个任务”。这里有几个关键词需要理清最大匹配包含边数量最多的匹配。通常我们关心的是在“尽量多的人被分配到任务”的前提下到底能分配多少对。完美匹配如果左右两个集合的顶点数量恰好相等并且某个匹配能覆盖左右两侧的所有顶点那么这个匹配就是完美匹配。完美匹配一定是最大匹配但最大匹配不一定是完美匹配。最大权匹配如果每条边还有权重我们希望在匹配边数最多的前提下让总权重尽量大。经典算法是KM算法它是匈牙利算法的一种扩展这篇文章先聚焦在无权场景。在实际业务里比如一个排课系统左侧是20门课右侧是20个教室我们希望尽量让每门课都分到教室。如果最后只匹配出16对那说明有4门课排不上得启用备用教室或者调整时间段。这就是最大匹配的价值——它告诉你在当前约束下能做到的极限。1.3 现实场景哪些问题本质上是二分图匹配二分图匹配的应用场景比想象中广泛得多。我列几个最常见的任务分配与资源调度。比如你有5台机器和5个订单每个订单只能由特定几台机器加工怎么排能让完成的订单最多这就是经典最大匹配问题。求职招聘匹配。左侧是候选人右侧是岗位边表示“该候选人符合该岗位的基础要求”。系统希望尽可能多的人拿到offer本质也是跑一遍最大匹配。相亲或社交推荐。如果要做一对一的匹配推荐比如某个兴趣交友活动需要尽量让参与的人都匹配到一个聊伴这也能建模成二分图。课程冲突检测。把学生分组和可用的时间段分别看作左右顶点冲突约束用边表示求最大匹配可以判断是否能避开所有冲突。车辆调度与路径规划。出租车和订单的分配外卖员和订单的分配在高峰期做全局最优分配时同样用得上。理解了这些场景再看匈牙利算法就不会觉得它只是个“练习题算法”了。它是很多推荐系统、调度系统背后的基础组件之一。2. 匈牙利算法的核心思路增广路径怎么找2.1 核心思想一句话匈牙利算法的核心可以浓缩成一句话从一个未匹配的左侧顶点出发不断寻找“增广路径”每找到一条就把当前匹配扩大一步直到再也找不到增广路径为止此时的匹配就是最大匹配。那什么是“增广路径”呢简单说一条增广路径是一条从左侧未匹配顶点出发依次交替经过“未匹配边、匹配边、未匹配边、匹配边……”最终到达另一个未被匹配的右侧顶点的路径。这条路径上未匹配边的数量恰好比匹配边多1。如果看不懂术语没关系用现实场景演算一遍就明白了。假设相亲活动里有3位男生和3位女生连线表示双方第一印象互有好感。现在的匹配状态是男生A匹配了女生X。此时一个未匹配的男生B对女生X也有好感而女生X已经匹配给了A。怎么办B先尝试把女生X“抢”过来但X不能同时配给两个人所以A被迫“让位”。A被让出后他发现自己还对女生Y也有好感而Y目前是单身状态。于是最终结果是B配XA配Y。这条“B - X - A - Y”的路径就是一条增广路径。走完这条路径后路径上的匹配关系发生了翻转原本匹配的边变成了不匹配原本不匹配的边变成了匹配。因为增广路径上不匹配边比匹配边多1条翻转后匹配数正好加1。2.2 增广路径为什么能增大匹配理解翻转操作是理解匈牙利算法的关键。我再用一个更形象的方式描述把匹配情况想象成一段路面上交替铺了两种砖一种叫作“已匹配边”的砖用实线表示一种叫作“未匹配边”的砖用虚线表示。一条增广路径就是一段从起点到终点、由实线和虚线交替铺成的路并且起点和终点两侧的砖一定是虚线。如果你把这段路上所有实线砖都挖掉换成虚线把所有虚线砖都换成实线你会发现整段路上的“实线砖”数量刚好增加了1。由于路径两端的顶点原本都未匹配翻转之后两端顶点被匹配了而中间顶点的度没有变所以整个匹配的稳定性没有被破坏只是匹配数增加了1。匈牙利算法反复寻找这样的路径直到整个图中找不到任何一条从左侧未匹配顶点出发、能到达右侧未匹配顶点的增广路径此时就达到了“饱和状态”也就是最大匹配。2.3 DFS实现的执行过程匈牙利算法有两个常用实现版本一个是基于深度优先搜索DFS一个是基于广度优先搜索BFS。DFS版本代码短、好理解适合边数不是特别夸张的场景也是我这次介绍的重点。DFS版本的思路是写一个递归函数dfs(u)它负责尝试给左侧顶点u找一个匹配点遍历u的所有邻接右侧顶点v如果v没有被访问过就标记访问过然后判断v是否处于未匹配状态或者已匹配的左侧顶点能通过递归找出一条增广路径。如果递归成功就把v匹配给u返回true。关键细节是visited标记数组。每一轮尝试匹配一个新的左侧顶点时visited数组都要重置。这个数组的目的是防止递归时出现死循环比如顶点A尝试匹配XX已匹配BB尝试匹配YY又指向X如果没有visited标记就会在X和Y之间来回递归。整个算法的主流程就是遍历左侧所有顶点对每个未匹配的顶点尝试调用dfs。只要dfs返回true最大匹配数就加1返回false说明这个顶点在当前匹配状态下无法找到合适对象只能跳过。3. Java实现匈牙利算法附完整代码3.1 邻接表版本的DFS实现在实际项目中二分图的规模通常不会太小所以推荐用邻接表存储图结构。下面是我在项目中经常使用的模板基于邻接表实现简洁且性能不错。import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class HungarianAlgorithm { // 左侧顶点数量 private int n; // 右侧顶点数量 private int m; // 邻接表left[i] 表示左侧第 i 个顶点可连接的右侧顶点集合 private ListListInteger adjacency; // matchRight[v] 表示右侧顶点 v 当前匹配的左侧顶点编号-1 表示未匹配 private int[] matchRight; // 每次尝试匹配时标记右侧顶点是否已被访问 private boolean[] visited; public HungarianAlgorithm(int n, int m) { this.n n; this.m m; this.adjacency new ArrayList(); for (int i 0; i n; i) { adjacency.add(new ArrayList()); } this.matchRight new int[m]; Arrays.fill(matchRight, -1); } /** * 添加一条边左侧顶点 u 和右侧顶点 v 之间可以匹配 */ public void addEdge(int u, int v) { adjacency.get(u).add(v); } /** * 尝试为左侧顶点 u 寻找匹配 */ private boolean dfs(int u) { for (int v : adjacency.get(u)) { if (visited[v]) { continue; } visited[v] true; // 如果 v 未匹配或者 v 当前的匹配对象可以换一个匹配则匹配成功 if (matchRight[v] -1 || dfs(matchRight[v])) { matchRight[v] u; return true; } } return false; } /** * 计算最大匹配数返回匹配数 */ public int maxMatch() { int result 0; for (int u 0; u n; u) { visited new boolean[m]; if (dfs(u)) { result; } } return result; } /** * 获取匹配结果返回值数组下标是右侧顶点编号值是对应的左侧顶点编号 */ public int[] getMatchResult() { return matchRight.clone(); } }3.2 代码逐段讲解这个模板有几个地方值得细说邻接表的选择。有人喜欢用二维布尔数组boolean[][] canMatch来表示可匹配关系这样代码更直观但稀疏图场景下很浪费空间。比如左侧有5000个点、右侧有5000个点全量标记数组就是2500万个布尔值无论在内存还是遍历效率上都不理想。邻接表只存储实际存在的边在稀疏场景下快很多。visited数组的更新位置。你可能会注意到visited数组在递归调用中标记的是右侧顶点。这是因为整个DFS过程中右侧顶点一旦被“尝试过”在当前这轮匹配中就不该被再次尝试。如果同一轮里重复访问同一个右侧顶点剩下的逻辑会陷入重叠递归最终可能导致死循环或者错误结果。matchRight[v] -1 || dfs(matchRight[v])这行是精华。它先看右侧顶点v有没有被占。如果没有被占直接让当前顶点u匹配v。如果被占也不代表结束而是尝试让v原来的匹配对象即matchRight[v]去找一个新的右侧顶点把v腾出来给当前的u。这就是“腾挪”的逻辑也是增广路径在代码层面的体现。复杂度分析。匈牙利算法最坏时间复杂度是O(N * E)其中N是左侧顶点数E是边的数量。如果左侧有1000个顶点边有10000条最坏情况大约需要执行1000 * 10000 10^7次操作Java跑下来也就几十毫秒到几百毫秒完全能覆盖大多数中小规模业务。3.3 时间复杂度和优化空间在实际使用中可以将visited的初始化从new boolean[m]改成数组复用例如用一个int[] visitedVersion和全局计数器version来判断某一轮是否访问过避免每轮都重建数组带来的GC压力。这是个微小但实用的优化尤其当顶点数量较大时能明显降低耗时。另外如果左侧顶点数量远大于右侧可以考虑在调用maxMatch之前调换左右集合让右侧成为遍历方向可能减少递归深度。原因是DFS的递归深度与左侧顶点的匹配链路长度有关从规模较小的一侧发起遍历整体递归层数通常更可控。4. 用Qt Creator调用匈牙利算法4.1 为什么要在Qt里调用很多桌面工具、上位机软件和工业调度界面是用Qt写的而业务判断逻辑如果用Java实现则需要解决跨语言调用的问题。热搜词里提到的 “qt creator调用匈牙利算法”本质上就是如何在C/Qt环境里实现或者接入这个算法。实际上有两个思路一种是用C重写一份匈牙利算法然后直接在Qt工程里调用另一种是通过JNI调用Java层的算法逻辑。我个人的建议是如果算法逻辑不复杂直接用C重写一份Qt版如果复杂的业务已经在Java后端里写好才考虑JNI桥接。C重写的好处是零依赖不用担心JVM环境也没有跨语言类型转换的麻烦。而且匈牙利算法本身很短重写成本极低。4.2 工程搭建与集成步骤下面我贴一段Qt/C版本的匈牙利算法接口方便你直接集成到自己的工程里。// hungarian.h #ifndef HUNGARIAN_H #define HUNGARIAN_H #include QVector class Hungarian { public: Hungarian(int leftCount, int rightCount); void addEdge(int left, int right); int maxMatch(); QVectorint matchResult() const; private: bool dfs(int left); int leftCount; int rightCount; QVectorQVectorint adjacency; QVectorint matchRight; QVectorbool visited; }; #endif // HUNGARIAN_H// hungarian.cpp #include hungarian.h Hungarian::Hungarian(int leftCount, int rightCount) : leftCount(leftCount) , rightCount(rightCount) , adjacency(leftCount) , matchRight(rightCount, -1) , visited(rightCount, false) { } void Hungarian::addEdge(int left, int right) { adjacency[left].append(right); } bool Hungarian::dfs(int left) { for (int right : adjacency[left]) { if (visited[right]) { continue; } visited[right] true; if (matchRight[right] -1 || dfs(matchRight[right])) { matchRight[right] left; return true; } } return false; } int Hungarian::maxMatch() { int result 0; for (int i 0; i leftCount; i) { visited.fill(false); if (dfs(i)) { result; } } return result; } QVectorint Hungarian::matchResult() const { return matchRight; }在Qt Creator里新建一个普通C类把上述两个文件加进工程然后在界面代码里引入头文件就可以使用了Hungarian h(5, 5); h.addEdge(0, 1); h.addEdge(0, 2); h.addEdge(1, 2); h.addEdge(2, 0); h.addEdge(2, 3); int matchCount h.maxMatch(); QVectorint result h.matchResult(); qDebug() 最大匹配数: matchCount;4.3 界面交互时的一些坑在Qt里集成算法时有几个问题我在实际开发中踩过提醒一下别把算法跑在UI线程里。如果匹配的顶点数达到几千甚至上万算法可能会计算几十到几百毫秒在极个别情况下甚至上秒。这个时间看起来不长但放在主界面线程里会造成界面卡顿用户会感觉窗口“假死”。碰到这种情况用QThread或者QtConcurrent::run把计算放到后台线程算完再通过信号槽把结果传回主界面刷新。注意左右顶点编号从0开始。界面展示给用户看的编号往往从1开始如果你在数据转换时忘记减1匹配结果会完全错乱。之前我遇到过用户反馈“明明有可行分配算法却告诉我匹配不上”排查半天发现是编号没对齐。数据更新时记得重置状态。如果界面上允许用户动态增删任务或执行者修改图结构后一定要重新构造Hungarian对象或者新增一个clear()接口把matchRight全部重置为 -1把邻接表清空否则上一轮匹配的残留状态会污染下一轮计算。5. 常见问题与排查实录5.1 递归太深导致栈溢出当左侧顶点数量很多、匹配链路又特别长时DFS递归深度可能达到几千层默认栈空间可能撑不住。这个问题在小数据量时几乎遇不到但当你处理上万规模的匹配时就要当心了。解决思路有两种一种是在代码里改用BFS版本BFS用队列替代递归从根本上避免栈溢出另一种是调大线程栈空间在启动参数中设置-XssJava或在Qt中通过QThread创建带自定义栈大小的子线程。我个人倾向于推荐BFS版本因为匈牙利算法的BFS实现虽然代码比DFS多一些但稳定性更好更适合生产环境。5.2 匹配结果不对先检查图是否真的是二分图匈牙利算法只能处理二分图。如果输入的图混入了同侧边或者环算法会得到错误结果而且这种错误有时候极具隐蔽性——在部分数据上是错的换一组数据又对了。排查方法很简单在加边的时候做一个检查只允许左侧顶点编号0到n-1连接到右侧顶点编号n到nm-1如果发现越界编号直接报错提示。或者干脆在算法执行前用染色法判断一下是否满足二分图性质。5.3 大数据量下的性能优化当左侧顶点数达到几万、边数达到几十万时普通DFS实现可能会变得很慢。这时候可以考虑几个优化手段使用BFS实现避免递归开销。对左侧顶点的遍历顺序做启发式调整优先处理邻接边数少的顶点。这个策略在二分图匹配里被称为 “small-degree-first”实测能明显减少匹配链路的长度。对于稠密图可以把邻接表换成位集bitset加速遍历但对稀疏图提升不大。5.4 如何优雅地输出匹配方案有些业务不只是要一个“匹配数量”还要求输出具体的配对关系。此时matchRight数组就是核心它的下标代表右侧顶点编号值代表匹配的左侧顶点编号。反过来也可以维护一个matchLeft数组方便左侧查询。如果界面需要展示匹配对我建议把匹配结果统一封装成一个结构体或对象而不是散落着两个数组否则后续维护和扩展都会很痛苦。public class MatchPair { int leftId; int rightId; // 其他业务字段... }6. 用匈牙利算法时我的一些个人体会这个算法写了无数遍之后最大的体会是它的代码实在太短了短到让人容易低估它背后的逻辑深度。如果你只是想跑通背模板就行但如果想真正用好它务必花时间把“增广路径”和“腾挪”这两个概念吃透。还有一个经常被忽略的点在实际项目里二分图往往不是现成的你需要自己建模。建模的质量直接决定算法的效果。比如在任务分配场景中判断“边是否存在”用什么标准是硬性条件还是软性偏好如果存在“一个人做多个任务”的需求传统匈牙利算法就没法直接用了需要改造成带容量限制的流网络或者把一个人拆成多个虚拟节点。我见过太多人一上来就套模板然后抱怨算法“不适用”其实往往是模型没建对。算法是工具箱里的那把螺丝刀能不能拧上螺丝还得看螺丝和木头的匹配关系对不对。另外如果你是Qt开发者建议先直接在纯C控制台工程里把算法跑通确认逻辑无误后再往界面工程里迁移。算法逻辑和UI代码混在一起调试时两边互相干扰特别容易劝退新手。最后分享一个调试小技巧给算法加上可视化输出把每一次匹配过程中访问过的节点路径打印出来。对于DFS实现只需在dfs函数的入口和出口分别打日志就能看到每一条增广路径的走向。这个做法在数据规模不大时极其好用比干看结果数组可靠得多。