二分图匹配这个名词听起来像是纯理论课里的概念，但只要你做过任务分配、课程排表、相亲平台推荐或者商家券派发这类需求，多半已经在跟它打交道了。匈牙利算法作为求解二分图最大匹配的经典算法，结构简单、代码量小，却能让一堆看似无从下手的问题瞬间清晰起来。这篇文章我会从“为什么需要它”开始讲，再手把手拆实现原理，给出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配X，A配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尝试匹配X，X已匹配B，B尝试匹配Y，Y又指向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 List<List<Integer>> 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(); QVector<int> matchResult() const; private: bool dfs(int left); int leftCount; int rightCount; QVector<QVector<int>> adjacency; QVector<int> matchRight; QVector<bool> 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; } QVector<int> 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(); QVector<int> 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用队列替代递归，从根本上避免栈溢出；另一种是调大线程栈空间，在启动参数中设置-Xss（Java）或在Qt中通过QThread创建带自定义栈大小的子线程。我个人倾向于推荐BFS版本，因为匈牙利算法的BFS实现虽然代码比DFS多一些，但稳定性更好，更适合生产环境。
5.2 匹配结果不对？先检查图是否真的是二分图
匈牙利算法只能处理二分图。如果输入的图混入了同侧边或者环，算法会得到错误结果，而且这种错误有时候极具隐蔽性——在部分数据上是错的，换一组数据又对了。
排查方法很简单：在加边的时候做一个检查，只允许左侧顶点（编号0到n-1）连接到右侧顶点（编号n到n+m-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函数的入口和出口分别打日志，就能看到每一条增广路径的走向。这个做法在数据规模不大时极其好用，比干看结果数组可靠得多。
