聊到图论里颜值和实用性并存的问题二分图匹配绝对排得上号。你手里有一堆任务、一堆人每个人只擅长其中某些任务想尽可能多地把任务安排出去这就是经典的二分图最大匹配问题而匈牙利算法是解决它最经典、也最容易上手的方法。这篇文章会把概念、原理、Python 实现和常见坑一次讲透适合正在学算法、准备竞赛或者在实际系统里写分配逻辑的人。即使你现在不需要手写先把思路理解透以后遇到任何“资源分配”类问题都能一眼看穿本质。1. 先搞清楚二分图匹配是怎么回事1.1 从任务分配场景理解二分图假设一个小团队里有 3 个开发者和 4 个需求每个开发者只愿意接手其中某几个需求。产品经理希望尽可能多地给需求分配负责人但一个需求只能交给一个人一个人也只能同时负责一个需求。把开发者放在左边一列需求放在右边一列只有“能接”的才连一条线你得到的图就是一个典型的二分图。“二分”的意思是可以把所有顶点分成左右两堆同一边的顶点之间永远没有边所有边都只连接左右两侧。这个结构在生活中非常常见求职者和岗位、学生和社团、课程和教室、快递员和订单全部可以建模成二分图。匹配是在这些边里挑出一组边要求任意两条边不能共享顶点。换句话说每个左点的度不超过 1每个右点的度也不超过 1。最大匹配就是能挑出来的边数最多的那一组。刚才的开发者和需求例子最后希望达到的效果就是“最多能包给几个需求”。1.2 三个核心术语二分图、匹配、最大匹配在正式编码前先把术语统一一下。二分图记作 G (L, R, E)其中 L 是左点集合R 是右点集合E 是连接左右的边。匹配记作 M它是 E 的子集且 M 中任意两条边没有公共端点。如果某个左点或右点出现在匹配的某条边上就称这个点是“被匹配的”否则叫“未匹配点”。最大匹配自然就是让 |M| 最大的匹配。更严格一点说最大匹配是“边数的最大可能值”而不是某个特定匹配结果。同一个图可能有多个不同的最大匹配但最大匹配的边数唯一。还有一个概念叫完美匹配指的是左点数量和右点数量相同且每个顶点都被匹配。完美匹配一定是最大匹配但最大匹配未必是完美匹配。区分这两个概念很重要因为很多初学者会把“最大匹配数等于 min(|L|, |R|)”当成默认结论实际上只有存在完美匹配时才成立。1.3 为什么最大匹配数量唯一但方案不唯一既然最大边数唯一那算法如果能输出任意一个达到这个数量的匹配就算正确。匈牙利算法做的就是这样的事情它不保证匹配方案唯一但一定保证匹配数最多。下面用一个简单的例子说明。左右各有 2 个点边是 L0-R0、L1-R0、L1-R1。最大匹配显然是 2但有两种方式得到呢其实只有一种L1-R1、L0-R0。再换一个图L0-R0、L0-R1、L1-R1最大匹配就是 2方案可以是 L0-R0、L1-R1也可以是 L0-R1、L1-R0。两者都能达到 2但中间过程不同。所以写代码时只需要保证答案计数正确匹配对象怎么选不影响最大性。从工程角度讲如果业务要求输出一个确定方案可以在算法里给左右点编号排序优先匹配编号小的点。这样同一份输入跑出来的结果就是稳定的。后面实现部分会提到这一点。2. 匈牙利算法原理如何一步步逼近最大匹配2.1 增广路匹配数1 的秘密匈牙利算法最核心的概念是增广路。增广路是一条路径它从某个未匹配的左点出发交替地走非匹配边、匹配边、非匹配边……最后到达某个未匹配的右点。注意这里的“交替”是硬性要求。路径上边的类型必须是一条非匹配边、一条匹配边、一条非匹配边这样轮换。为什么非要这样因为这条路径经过取反操作后可以让匹配边数增加 1。取反操作非常简单把路径上的匹配边全部变为非匹配边把非匹配边全部变为匹配边。由于路径起点和终点都是未匹配点而且非匹配边数量比匹配边数量多 1所以取反后路径上的匹配边数量会比原来多 1整张图的匹配数也就跟着多 1。这就是匈牙利算法的直观想法不断寻找增广路找到一次就扩大一次匹配直到找不到增广路为止。这时当前匹配就是最大匹配。2.2 连锁换座给新人腾位置增广路理解起来有点抽象打个比方就清楚了。想象电影院里已经坐了一排观众每个人都有一个固定座位但还有新人想加入。新人可以先占一个空位如果这个空位已经被某人坐了那个人就挪到他喜欢的另一个座位如果那个座位又被另一个人坐了再继续往后挪。最终只要有一串人依次换座新人就能坐下整个影厅就多接待了一个人。在二分图匹配里每个左点就是“人”每个右点就是“座位”边代表“这个人愿意坐这个座位”。已经匹配的左点相当于“已经坐下的人”未匹配右点相当于“空座位”。DFS 里的递归过程本质就是在模拟这条换座链。比如 L0 已经匹配了 R0现在 L1 也想匹配 R0。算法不会直接把 L0 踢掉而是尝试给 L0 找另一个可用的座位 R1。如果 R1 空着成功如果 R1 也被 L2 占了就再给 L2 找。这就是一个以 L1 为起点、R1 或更远空位为终点的增广路。2.3 为什么循环增广一定能得到最大匹配这里需要回答一个关键问题找不到增广路时当前匹配真的是最大匹配吗答案是肯定的。原因可以用反证法说明。假设当前匹配 M 不是最大匹配那么一定存在另一个匹配 M使得 |M| |M|。把两个匹配画在同一张图上考虑它们的对称差也就是只在其中一个匹配中出现的边构成的结构。在二分图里这个结构只能由一些“交替路径”和“偶环”组成。因为 |M| 比 |M| 大对称差中一定至少有一条路径它的起点和终点都是 M 的匹配边而这条路径相对 M 来说就是一条增广路。换句话说如果 M 不是最大匹配则必然存在关于 M 的增广路。所以“不存在增广路”和“已经是最大匹配”是等价的。这个证明不用死记但需要理解它的逻辑匈牙利算法的终止条件是找不到增广路而这个条件意味着没有更大的匹配存在因此算法必然收敛到最大值。2.4 算法复杂度与两种常见实现方式最朴素的匈牙利算法做法是依次枚举每个左点从它开始 DFS 或 BFS 找增广路。每轮找路的过程会遍历与该左点相连的边并且递归地检查其他左点可以选择的边整体复杂度是 O(VE)其中 V 是左点或右点数量E 是边数。在最坏情况下V 和 E 都是数千甚至上万时O(VE) 可能达到千万到亿级别但实际运行时通常远小于最坏情况。两种实现方式各有侧重。DFS 版代码极短理解和记忆成本低是竞赛和面试的首选BFS 版需要用队列维护“换座顺序”代码更长但可以避开递归栈深度问题。在 Python 里如果递归深度不够或者图形成了很深的链式结构DFS 版可能爆栈这时可以改用 BFS 版。后文会分别给出实现。3. Python 手写匈牙利算法3.1 图的存储与输入处理实现前先定好数据格式。左右点都从 0 开始的整数编号邻接表 adj[u] 存放左点 u 可以匹配的所有右点编号。下面是一个最小示例edges [(0, 0), (0, 1), (1, 1), (1, 2), (2, 0), (2, 2)] n_left 3 n_right 3 adj [[] for _ in range(n_left)] for u, v in edges: adj[u].append(v)如果输入是 1 开始的编号先统一减一。如果左右点编号空间相同也可能冲突后文会专门讲这个问题。无论编号怎么变只要保证左点编号用于 match_right 的下标索引没问题右点编号用于 visited 列表即可。3.2 DFS 版匈牙利算法最经典、最简短的实现如下def hungarian_dfs(adj, n_left, n_right): match_right [-1] * n_right def dfs(u, visited): for v in adj[u]: if visited[v]: continue visited[v] True if match_right[v] -1 or dfs(match_right[v], visited): match_right[v] u return True return False ans 0 for u in range(n_left): visited [False] * n_right if dfs(u, visited): ans 1 return ans, match_right核心就两三行。每当尝试匹配左点 u 时遍历所有可以选择的右点 v。如果 v 还没被匹配直接占住如果 v 已经被某个左点 pre 匹配就递归地尝试给 pre 寻找新的右点。如果 pre 能找到新位置就把 v 让给 u整体匹配数加 1。注意 visited 数组每轮都要重置。它标记的是“本轮尝试中已经访问过的右点”防止递归在多个左点之间反复横跳形成死循环。如果不重置后续左点就无法访问之前尝试过的右点会严重漏解。这段代码默认每个左点都要尝试一遍即使它已经匹配了也可以再次进入 DFS因为依然可能找到一条新的增广路让总匹配数继续增加。如果你想优化常熟可以先判断这个左点是否已匹配但没必要反正对最大匹配没有影响。3.3 BFS 版匈牙利算法BFS 版没有递归用队列模拟换座过程。它需要额外维护一个 pre 数组记录每个左点是从哪个左点转移过来的回溯时才能完整更新匹配关系。from collections import deque def hungarian_bfs(adj, n_left, n_right): match_left [-1] * n_left match_right [-1] * n_right pre [-1] * n_left def bfs(root): q deque([root]) pre[root] -1 seen_right [False] * n_right while q: u q.popleft() for v in adj[u]: if seen_right[v]: continue seen_right[v] True w match_right[v] if w -1: # 找到一个未匹配的右点沿着 pre 回溯换座 while u ! -1: prev_u pre[u] old_v match_left[u] match_right[v] u match_left[u] v v old_v u prev_u return True pre[w] u q.append(w) return False ans 0 for u in range(n_left): if bfs(u): ans 1 return ans, match_left这段代码理解起来比 DFS 难一点。关键在于队列里放的都是左点每访问一个右点 v 时如果 v 当前匹配给了 w就把 w 入队意思是“w 可能需要换到别的座位”。同时记录 pre[w] u表示 w 是从 u 这条路径发现的。最后如果遇到空位 v就可以沿着 pre 一路回溯把所有冲突的左点依次挪动。BFS 的优势是栈深度可控适合 n 很大或递归层级很深的场景。缺点是代码容易写错尤其是回溯那段建议先在草稿纸上画 3 个左点、3 个右点的链式例子走一遍逻辑再上机。3.4 DFS 版和 BFS 版怎么选对于大多数竞赛题和业务场景DFS 版就够用了。Python 默认递归深度只有 1000如果左点数量在 1000 以上或者图很深需要手动加sys.setrecursionlimit(1000000)。如果不想依赖递归就用 BFS 版。下面的表格总结了两个版本的差别对比项DFS 版BFS 版实现难度低代码短中需要 pre 回溯递归栈风险高深度大时可能爆栈无递归安全理解成本适合初学者需要结合队列理解实际性能通常很快与 DFS 基本同级别推荐场景竞赛、面试、小规模图大规模图、递归受限环境如果你只是实现一次最大匹配不追求极限性能DFS 版是收益最高的选择。如果你要在生产系统里长期处理上万个节点可以考虑使用 Hopcroft-Karp 算法它把复杂度优化到 O(E√V)但这篇文章不展开先把匈牙利算法吃透更重要。4. 常见应用与实战案例4.1 任务分配与资源调度任务分配是最直接的应用。左边是工人右边是任务边表示“能做”最大匹配就是“最多能安排多少任务”。类似地快递站可以把配送员和订单做匹配减少空跑服务系统可以把客服和排队用户做匹配尽量让每个客服接单。这类问题在工程里有个隐藏陷阱匹配结果可能不稳定。如果你只告诉系统“有 5 个任务可以安排”但没指定哪个任务给谁不同运行次序会得到不同方案。如果要稳定输出可以在 DFS 遍历邻接表前把右点编号排序或者在遍历左点前排序让算法总是优先匹配编号较小的一方。4.2 最小点覆盖、最大独立集、最小路径覆盖匈牙利算法不止能解决最大匹配本身借助二分图的几个经典定理它还能解决一批看起来完全不同的问题。第一个是 König 定理在二分图中最小点覆盖的大小等于最大匹配的大小。最小点覆盖是选尽量少的点让每条边至少有一个端点被选中。这个定理非常有用因为很多“消灭边”的问题都能转化为最小点覆盖。第二个是最大独立集。独立集是选出尽量多的点使这些点之间没有边相连。在二分图中最大独立集的大小等于总点数减去最大匹配数。直观理解覆盖了所有边的点集合如果去掉剩下的点之间不可能有边因此是独立集而为了独立集最大被去掉的点要最少。第三个是最小路径覆盖。给定一个有向无环图要求用最少的不相交路径覆盖所有顶点。做法是把每个点拆成两个点一个作为左点一个作为右点原图中的边 u-v 转化为左 u 连右 v然后求最大匹配。最小路径覆盖数 顶点数 - 最大匹配数。这三个变型经常出现在网络流、任务调度和状态压缩的题目里掌握它们成就感会非常强。4.3 实战案例分析教室排课假设有一个系统要给课程分配教室。左边是课程右边是教室边表示“该教室在这个时间段可用”。每门课需要一个教室每个教室只能给一门课目标是尽可能多地排上课。比如有 5 门课4 个教室邻接表如下adj [ [0, 1], # 课程0 可上教室0或1 [0, 2], # 课程1 可上教室0或2 [2, 3], # 课程2 可上教室2或3 [1, 3], # 课程3 可上教室1或3 [0, 1, 2, 3], # 课程4 哪个教室都行 ] n_left 5 n_right 4用上面的 DFS 版跑一遍得到最大匹配数应该是 4因为有 5 门课 4 个教室最多只能排 4 门。输出 match_right 后可以看到具体是哪 4 门课被排上了。如果业务要求优先安排高优先级课程可以把课程按优先级排序后再执行算法如果需要每间教室容量不同那就需要把每个容量看成多个教室副本。这类“最多能匹配多少”的需求在现实中非常普遍。排课系统、工单分配、相亲配对底层都是同一套模型。理解这个案例你就能把各种业务问题快速映射成二分图匹配。5. 常见问题与排查技巧5.1 匹配结果偏小的常见原因很多同学照着模板写结果总是比预期少 1 或 2。最常见的罪魁祸首是 visited 数组没有在每轮左点尝试之前重置。每轮 DFS 必须新建一个[False] * n_right否则之前访问过的右点会被跳过增广路找不到。第二个常见原因是递归里访问条件写错。有些人会把 visited 标记在 match_right[v] 对应的左点上这会导致同一轮内不同左点互相屏蔽。正确做法是只要右点 v 已访问就直接跳过不再尝试从它出发。第三个原因是遍历邻接表时只看了第一项就 return。DFS 里必须遍历所有边只有当所有可选项都试过且失败时才返回 False。如果提前返回会漏掉后面的增广路。5.2 左右编号冲突与重边问题当左点和右点都是 0 开始的整数编号时最方便的做法是分别用两个数组 match_left 和 match_right而不是共用一个 match 数组。visited 数组也只对右点生效。如果左右点共享同一套状态很容易出现“访问过右点却当成左点标记”的低级 bug。重边在一般情况下不会造成问题因为 DFS 里重复访问同一个右点会被 visited 拦住。但大量重边会浪费时间建议在建图时去重可以用集合替代列表。孤立点完全不影响算法只是不会形成匹配。如果左点数量远大于右点数量也可以考虑把点和边的方向翻转让较少的点作为左点这样外层循环次数更少效率更高。5.3 递归栈溢出与性能优化Python 默认递归深度约为 1000当图有上万个左点且增广路很长时DFS 版很容易触发 RecursionError。解决方法是开头设置sys.setrecursionlimit(10 ** 6)。但要注意递归层数太深依然可能让解释器崩溃更稳妥的做法是切换到 BFS 版。如果图的规模很大匈牙利算法 O(VE) 会显得吃力。此时可以改用 Hopcroft-Karp 算法它每次先做 BFS 构建分层图再一次性寻找多条最短增广路时间复杂度降为 O(E√V)。这个属于进阶内容但知道它存在很有用。5.4 快速自测模板与速查表写完实现后建议用几个小例子自测。下面这个是最简单的最大匹配为 2 的例子# L0-R0, L1-R0, L1-R1 adj [[0], [0, 1]] n_left 2 n_right 2 # 期望输出 2再测一个最大匹配只有 1 的例子# 左右各2个点只有一条边 L0-R0 adj [[0], []] n_left 2 n_right 2 # 期望输出 1如果这两个例子都能通过再换左右数量不平衡的大样例做压力测试基本就不会有大问题了。总结一下常见问题症状可能原因解决方案结果偏小visited 未重置每轮新开 visited 数组结果偏小递归提前 return遍历全部邻接边后再判失败递归报错深度超过默认限制设置递归深度或改用 BFS匹配方案不对左右编号共用状态分开 match_left / match_right性能太差图太大改用 Hopcroft-Karp 或拆点优化死循环visited 标记错误正确标记右点访问状态最后分享一个我自己写这类算法的经验不要一行行背模板而是把增广路的“换座”逻辑在纸上走通。我实际开发里用 DFS 版最多因为短、不容易出错真正让我踩坑的是没有区分左右点编号空间导致 visited 标记错对象调试了整整一个下午。后来我在建图之前就单独写一个点编号映射函数把左右点统一规范成各自从 0 开始这类问题就再也没出现过。还有一个很有用的技巧如果你需要稳定输出匹配方案可以对邻接表里的右点排序后再执行 DFS这样同一份输入在任何机器、任何运行次数下得到的结果都一样。生产环境里一致性和最优性同样重要这种细节往往比算法本身更考验工程能力。