1. 从“相亲配对”到“任务调度”二分图到底是什么如果你听说过“匈牙利算法”或者被“最大匹配”、“最小点覆盖”这些词绕晕过那多半是遇到了二分图相关的问题。我第一次接触这个概念是在解决一个简单的任务分配问题时有5个工人和5台机器每个工人只会操作特定的几台机器怎么安排才能让尽可能多的机器被操作起来这个问题抽象一下工人和机器就是两类不同的点工人和他能操作的机器之间连上线就构成了一张典型的二分图。所以二分图的核心思想很简单把研究对象分成两个互不相交的集合所有关系边都只存在于这两个集合之间集合内部没有直接关系。这种“非黑即白”的划分让它成为建模“匹配”类问题的绝佳工具从相亲网站的用户推荐、到云计算中的虚拟机调度底层逻辑都可能藏着二分图。很多人觉得二分图的理论复杂各种定理和概念像绕口令。其实只要抓住“匹配”这个核心一切都能串起来。你可以把匹配想象成“一对一牵手”一个工人只能操作一台机器一台机器也只能被一个工人操作。我们的目标就是找到最多的这种“牵手”关系这就是最大匹配。而围绕最大匹配衍生出了一系列紧密相关的概念为了保证所有边都被“管住”最少需要选多少个点最小点覆盖为了选出最多的互不相连的点最大独立集以及如何用最少的路径覆盖所有点最小路径覆盖。最奇妙的是这几个看似不同的问题在二分图的世界里通过König定理被深刻地联系在了一起常常是“知一求三”。这篇总结的目的就是帮你把这些散落的知识点用一条清晰的逻辑线穿起来。我们不只讲定义和算法更重点讲清楚它们为什么是等价的证明的思路是什么以及面对一道题时如何快速判断它是个二分图问题并选用正确的模型和算法解决。无论是刚入门的小白还是想梳理进阶知识的同学都能从这里找到一条从理解到实战的路径。2. 二分图的判定与建模如何认出它并把它画出来在动用各种高级算法之前第一步永远是你面对的问题是不是一个二分图问题如何把它抽象成二分图模型2.1 二分图的定义与判定算法形式化定义对于一个无向图 G(V, E)如果能把顶点集 V 分成两个不相交的子集 U 和 V使得图中的每一条边 (u, v) 都满足 u 属于 U 且 v 属于 V或者反之那么图 G 就是一个二分图。集合 U 和 V 通常被称为“左部点”和“右部点”。如何判定一个给定的图是不是二分图呢核心原理在于二分图等价于不含奇数环长度为奇数的环的图。为什么想象一下你从一个点出发把它染成黑色它的所有邻居必须染成白色邻居的邻居又必须染回黑色……如果这个图是二分图这个染色过程应该不会出现矛盾即不会有一个点既被要求染成黑色又被要求染成白色。出现矛盾的情况只可能是在遍历中遇到了一个奇数环导致绕了一圈回来颜色冲突。基于这个原理最常用的判定方法是深度优先搜索DFS或广度优先搜索BFS染色法。// 使用DFS进行二分图判定邻接表存储 vectorint color; // 0表示未染色1和-1表示两种颜色 vectorvectorint graph; bool isBipartite(int n) { // n为顶点数 color.assign(n, 0); for (int i 0; i n; i) { if (color[i] 0) { // 对每个未访问的连通分量进行DFS if (!dfs(i, 1)) { return false; } } } return true; } bool dfs(int u, int c) { color[u] c; for (int v : graph[u]) { if (color[v] 0) { // 邻居未染色染成相反颜色 if (!dfs(v, -c)) return false; } else if (color[v] c) { // 邻居颜色相同冲突 return false; } } return true; }实操心得在实际做题时图不一定是以显式的“边列表”形式给出。很多时候你需要从问题描述中自己构建图。一个关键技巧是寻找“互斥”或“二选一”的关系。例如如果题目描述涉及“不能共存”、“冲突”、“交替”等词语往往暗示着二分图模型。把互斥的双方分别作为左部点和右部点它们之间的冲突关系就是边。2.2 常见问题建模举例棋盘覆盖问题在一个国际象棋棋盘或MxN网格上放置骨牌1x2或者处理棋盘上禁止放置的格子。经典建模是按坐标和的奇偶性染色。将(ij)为偶数的格子作为左部点奇数的作为右部点。如果两个格子相邻可被一张骨牌覆盖则在它们之间连边。这样骨牌覆盖就转化为了寻找最大匹配。任务分配/人员安排如前所述左边是人员或任务右边是资源或时间段边表示“有能力完成”或“可用”。这是最直接的二分图模型。冲突图着色例如安排课程或会议有冲突的课程不能同时进行。这通常不是直接的二分图但它的补图如果两个事件不冲突则连边可能是二分图可以用于解决一些特殊约束下的问题。注意判定算法复杂度通常是O(VE)。在建模时务必注意顶点规模。有时直接建边会导致边数爆炸例如左部每个点都可能连接右部大部分点这时需要考虑是否能用更高效的方式如贪心解决或者利用问题特性优化建边例如利用区间性质用线段树优化连边。3. 匈牙利算法求解二分图最大匹配的经典手算思维这是二分图领域最著名、最直观的算法其核心思想是“腾挪”与“协商”非常符合人的直觉。3.1 算法核心增广路与“撬墙角”首先理解增广路在当前的匹配方案下一条从非匹配点出发依次经过非匹配边、匹配边、非匹配边……最终到达另一个非匹配点的路径。这条路径的特点是“非匹配边和匹配边交替出现”并且起点和终点都是未匹配的点。关键性质将增广路上的所有边状态取反匹配边变非匹配非匹配边变匹配匹配数恰好增加1。这就像一条“增广”匹配的路径。匈牙利算法就是不断寻找增广路直到找不到为止。寻找过程采用DFS从左部一个未匹配点u开始尝试匹配。遍历u的所有邻接点v。如果v未被匹配则直接匹配(u, v)找到一条增广路。如果v已被匹配设其匹配对象为match[v]则我们尝试“递归地”为match[v]寻找新的匹配。如果能为match[v]找到新的匹配点那么v就可以“让出来”给u。这相当于沿着匹配边“撬墙角”。如果为u找到了任何一个可匹配的v则匹配成功匹配数加一。// 匈牙利算法核心DFS函数 vectorint matchR; // 记录右部点匹配的左部点编号-1表示未匹配 vectorbool used; // 在单轮DFS中标记右部点是否已被访问防止死循环 bool dfs_hungarian(int u) { for (int v : graph[u]) { if (!used[v]) { used[v] true; // 如果v未匹配或者能给v当前匹配的对象找到下家 if (matchR[v] -1 || dfs_hungarian(matchR[v])) { matchR[v] u; // 匹配成功 return true; } } } return false; } int hungarian(int nLeft) { matchR.assign(m, -1); // m是右部点数量 int result 0; for (int u 0; u nLeft; u) { used.assign(m, false); // 每轮DFS重置访问标记 if (dfs_hungarian(u)) { result; } } return result; }为什么需要used数组这是算法正确性的关键。在一轮为u寻找增广路的过程中used[v]标记了右部点v是否已经被本轮尝试“访问”过。如果访问过说明已经为v尝试过寻找增广路但失败了无需重复尝试否则会导致无限递归。这个标记是每轮DFS独立的所以每次调用dfs_hungarian(u)前都要重置。3.2 算法复杂度与优化朴素匈牙利算法的时间复杂度是O(V * E)其中V是左部点数量。对于稠密图这个复杂度可以接受。对于点数较多如上千的稀疏图这个复杂度可能偏高。一个重要的优化是“全局vis数组”。在有些实现中会用时间戳int vis[maxn]和int dfn来代替每轮重置的bool used数组。每轮DFS开始时dfn访问右部点v时标记vis[v] dfn。这样判断条件变为if(vis[v] ! dfn)避免了O(V)的数组重置开销常数更优。实操中的坑点顶点编号确保左部点和右部点的编号体系不冲突。通常左部点从0到n-1右部点从0到m-1matchR数组大小为m。递归深度DFS实现简单但在极端情况下如链式图可能递归很深导致栈溢出。可以考虑用栈模拟递归或使用BFS实现的Hopcroft-Karp算法见下文。清空匹配多组数据输入时务必清空matchR数组和图的邻接表。4. Hopcroft-Karp算法用BFS分层加速匹配过程当图的规模变大时比如左右部点各有几千个O(V*E)的匈牙利算法可能显得吃力。Hopcroft-Karp (HK) 算法通过同时寻找多条最短增广路将复杂度降到了O(sqrt(V) * E)在稀疏图上优势明显。4.1 算法流程BFS分层 DFS多路增广HK算法的核心是“轮”的概念。每一轮包含两个阶段BFS分层从所有未匹配的左部点出发进行BFS目的是找出当前所有可能的最短增广路的长度并为图分层。定义距离dist左部未匹配点的初始距离为0。BFS遍历规则只能沿着非匹配边从左部走到右部再沿着匹配边从右部走回左部。这个过程会形成一个分层图。如果在BFS过程中遇到了一个未匹配的右部点说明找到了一条增广路记录下它的长度即BFS的层数。DFS多路增广利用BFS得到的分层信息dist从每个未匹配的左部点出发进行DFS寻找增广路。DFS的规则是只能从距离为d的左部点走到距离为d1的右部点然后从距离为d1的右部点通过匹配边走到距离为d2的左部点。这保证了DFS找到的增广路都是最短的。这一阶段会尝试用DFS找出所有互不相交的最短增广路即没有公共顶点并同时进行增广。一轮结束后匹配数增加的数量等于本轮找到的增广路条数。然后开始新的一轮BFS直到某一轮BFS无法到达任何未匹配的右部点即找不到增广路为止。4.2 为什么HK算法更快复杂度证明直觉匈牙利算法每次只找一条增广路而且可能绕远路。HK算法每一轮都找出所有长度相等的最短增广路然后一次性增广。 关键引理最短增广路的长度在算法执行过程中是单调递增的。每一轮增广后剩余的最短增广路长度至少增加2。 因此最短增广路的长度最多有O(sqrt(V))种因为每次找到的增广路长度递增且最长的增广路长度不超过V。每一轮中BFS和DFS的总复杂度是O(E)。所以总复杂度为O(sqrt(V) * E)。代码实现要点// 伪代码框架示意 int hopcroftKarp() { int matching 0; while (bfs()) { // BFS构建分层图并判断是否存在增广路 for (每个左部未匹配点 u) { if (dfs(u)) matching; // DFS尝试增广 } } return matching; }实现时需要维护左部点的dist数组并在DFS后及时更新匹配关系。HK算法的代码比匈牙利稍复杂但模板化程度高一旦掌握解决大规模二分图匹配问题会非常高效。选择建议在竞赛或面试中如果顶点数在几百量级用匈牙利算法足矣代码简单不易错。如果顶点数达到几千甚至上万并且是稀疏图一定要考虑使用Hopcroft-Karp算法。5. König定理连通最大匹配、最小点覆盖、最大独立集的金桥这是二分图理论中最优美、最重要的定理之一它揭示了三个不同问题之间的等价关系。理解它能让你在解题时拥有“降维打击”的能力。5.1 定理陈述与证明思路König定理在二分图中最大匹配数 最小点覆盖数。点覆盖选取图中的一个点集使得图中每一条边都至少有一个端点在这个点集中。点数最少的点覆盖就是最小点覆盖。最大匹配我们已经很熟悉了。证明思路构造性证明也是算法基础先求出二分图的一个最大匹配M。从所有左部未匹配点出发进行交替路遍历类似匈牙利算法中的DFS但只遍历不修改匹配。沿着未匹配边从左部走到右部。沿着匹配边从右部走回左部。标记所有在遍历过程中访问到的点。构造点集C取所有未被标记的左部点。取所有被标记的右部点。可以证明这个点集C就是一个最小点覆盖并且其大小等于最大匹配数|M|。为什么这样构造的点集C能覆盖所有边考虑任意一条边(u, v)其中u在左部v在右部。只有四种情况u被标记v被标记那么v在C中边被覆盖。u未被标记v未被标记如果(u, v)是匹配边那么u是匹配点从未匹配点出发的遍历如果走到v一定会走到u导致u被标记矛盾。如果(u, v)不是匹配边那么可以从某个未匹配左部点走到u因为u未被标记说明走不到但走到u后可以通过边(u, v)走到v导致v被标记矛盾。所以这种情况不存在。u被标记v未被标记如果(u, v)是匹配边那么从v通过匹配边一定会走到u导致v被标记矛盾。所以(u, v)不是匹配边。但u被标记了说明存在一条交替路到达u且最后一条边是匹配边这里需要仔细分析交替路定义。实际上通过反证法可以证明这种情况下边(u,v)一定被覆盖要么u是未标记左部点的匹配点更严谨的证明需要形式化。经典结论是这样构造的C一定能覆盖所有边。u未被标记v被标记那么u在C中所有未被标记的左部点边被覆盖。因此集合C覆盖了所有边。并且C中每个点都“对应”一条匹配边右部被标记点对应其匹配边左部未被标记点也对应其匹配边且不同的点对应不同的匹配边所以|C| |M|。又因为点覆盖数至少需要|M|每条匹配边都需要一个点来覆盖所以C是最小点覆盖。5.2 最大独立集与最小路径覆盖一旦理解了König定理另外两个概念就很容易了。最大独立集在图中选取最多的点使得这些点之间两两没有边直接相连。定理最大独立集 总顶点数 - 最小点覆盖。直观理解最小点覆盖是“破坏”所有边所需的最少点。把这些点去掉剩下的点之间肯定没有边因为边都被“破坏”了它们就构成了一个独立集。因为去掉的是最少的点所以剩下的就是最多的点即最大独立集。求法先求最小点覆盖集C那么最大独立集就是 V \ C。最小路径覆盖DAG在一个有向无环图中用最少的不相交顶点不相交的路径覆盖所有顶点。二分图建模将原DAG的每个顶点i拆成两个点左部点i代表起点、右部点i‘代表终点。如果原图中有边 i - j则在二分图中从左部i向右部j’连一条边。定理最小路径覆盖数 原图顶点数 - 拆点后二分图的最大匹配数。直观理解初始状态每个点自成一条路径共n条。二分图中的一次匹配代表将两条路径首尾相接i - j路径数减少1。最大匹配意味着最多可以进行多少次这样的合并因此剩下的路径数最少。例题思路点拨遇到“选最多互不冲突的点”、“用最少资源监控所有关系”、“用最少链覆盖序列”这类问题要立刻联想到二分图的这几个模型。先判断是否是二分图然后根据问题选择求最大匹配、最小点覆盖还是最大独立集。6. 最大权匹配KM算法与费用流转化当二分图的边上带了权重我们不再满足于找到最多的匹配而是希望找到所有匹配边权重之和最大的匹配这就是最大权匹配。对于完备匹配左右部点数相等且存在完美匹配情况下的最大权匹配有经典的Kuhn-Munkres算法即KM算法。6.1 KM算法的核心顶标与相等子图KM算法要求二分图是完备的可以通过补虚点和权重为0的边实现。它引入了一个非常巧妙的“顶标”概念。顶标给每个左部点i分配一个顶标lx[i]给每个右部点j分配一个顶标ly[j]。初始时通常令lx[i] max(weight[i][j])即从i出发的最大边权ly[j] 0。相等子图在原图的基础上只保留满足lx[i] ly[j] weight[i][j]的边(i, j)构成的子图。核心定理如果相等子图中存在完美匹配那么这个完美匹配就是原图的最大权完美匹配。KM算法就是通过动态调整顶标不断扩大相等子图直到相等子图中存在完美匹配。调整的原则是在保证已匹配边仍在相等子图中的前提下即不减少lx[i] ly[j]让更多的边进入相等子图即让一些lx[i] ly[j] weight[i][j]的边其差值变小。6.2 算法步骤与DFS/BFS实现传统的KM算法采用DFS实现思路类似匈牙利算法但在寻找增广路失败时会进行顶标调整。初始化顶标。为每个左部点尝试寻找匹配DFS。在DFS过程中只走相等子图中的边。如果对于左部点u找不到增广路则需要调整顶标。令delta min{ lx[i] ly[j] - weight[i][j] }其中i在本次DFS访问过的左部点集合中j在本次DFS未访问过的右部点集合中。将所有访问过的左部点的顶标减去delta。将所有访问过的右部点的顶标加上delta。这样操作后原来在相等子图中的边访问过的左-访问过的右依然满足等式因为一减一加原来不在相等子图中的、且i访问过、j未访问过的边其lxly-weight减少了delta可能变为0从而进入相等子图同时为访问过的左部点连接未访问过的右部点创造了可能。重复步骤2-4直到所有左部点都匹配成功。DFS实现的KM算法复杂度为O(n^3)其中n为点数。对于稠密图边数接近n^2且需要最大权匹配时KM算法是首选。BFS实现与Slack优化DFS实现中每次调整顶标后需要重新DFS可能重复遍历。BFS实现的KM算法常被称为“匈牙利树”方法以及引入slack数组记录最小值可以将复杂度稳定在O(n^3)但常数更优是竞赛中的标准模板。// KM算法核心代码框架BFSSlack优化 bool bfs(int u) { // 初始化slack数组为INF // 模拟BFS过程在相等子图中寻找增广路 // 如果找不到计算delta min(slack[j])调整顶标 // 调整后一些slack[j]变为0对应的右部点j加入考虑范围 // 循环直到找到增广路或确认无法找到 }重要限制KM算法通常用于求最大权完美匹配。如果只是求最大权匹配不要求完美或者图不是完备二分图一般将其转化为最小费用最大流问题来求解更加通用。6.3 转化为最小费用最大流模型这是一个非常强大的技巧可以解决带权二分图的各种匹配问题包括但不限于最大权匹配、最大权完美匹配、指定匹配数量的最大权匹配等。建模方法建立超级源点S超级汇点T。从S向每个左部点连边容量为1费用为0。从每个右部点向T连边容量为1费用为0。对于二分图中的每条边(u, v, w)从左部点u向右部点v连边容量为1费用为**-w**如果求最大费用则费用为w求最小费用最大流时我们通常将最大权转化为最小费用所以加负号。在图上跑最小费用最大流。最大流保证了匹配数最小费用即负的最大权重和则对应了最大权匹配。这种方法虽然复杂度比专门的KM算法高通常为O(F * E * logV)或SPFA的O(VE)但通用性强尤其适用于左右部点数不等、有特定容量要求比如一个左部点可以匹配多个右部点的复杂情况。7. 综合例题剖析从建模到求解的完整思考链路理论讲完了我们来看几个经典例题把前面的知识串起来。7.1 例题一棋盘放置最大匹配/最小点覆盖问题一个N*M的棋盘某些格子禁止放置。你拥有无数个1x2的骨牌骨牌可以水平或竖直放置。一个骨牌必须覆盖两个相邻的非禁止格子。问最多能放多少个骨牌。分析与建模判断模型骨牌覆盖两个相邻格子是典型的“匹配”问题。每个骨牌匹配两个格子。二分图构建将棋盘按(ij)的奇偶性黑白染色。所有黑色非禁止格作为左部点白色非禁止格作为右部点。如果两个相邻格子都是非禁止格则在它们之间连一条边。问题转化求这个二分图的最大匹配。每个匹配对应一个骨牌。求解使用匈牙利算法或Hopcroft-Karp算法求解最大匹配数即可。扩展如果问题变成“最少需要多少个骨牌才能覆盖所有可覆盖的格子”这等价于求最小边覆盖。有公式最小边覆盖 顶点数 - 最大匹配。7.2 例题二任务安排最小点覆盖/最大独立集问题有m个任务和n台机器。每个任务必须在给定的两台指定机器中的一台上运行。每台机器在同一时间只能运行一个任务。问是否存在一种安排使得所有任务都能被执行。分析与建模判断模型任务和机器是两类实体。每个任务需要两台机器中的一台这是“选择”关系。但机器有互斥性一个机器只能运行一个任务。这可以转化为冲突图。二分图构建将每个任务拆成两个点分别代表它选择机器A和选择机器B。但这会形成任务内部点的冲突更好的建模是以任务为边以机器为点。实际上这是一个图着色或匹配问题。更经典的建模是把任务看作边连接两台它需要的机器。那么问题转化为能否为每条边任务分配一个端点机器使得每个点机器最多被分配一条边任务这就是在原图的补图上找匹配不这实际上是在原图上找边覆盖的某种形式让我们重新思考。更清晰的二分图建模左边是任务右边是机器。任务i向它可用的两台机器连边。我们需要为每个任务分配一台机器且每台机器最多被分配一个任务。这就是标准的二分图匹配问题我们要求一个匹配其大小等于任务数m即完美匹配覆盖所有左部点。问题转化判断该二分图是否存在大小为m的匹配即左部完全匹配。跑一遍最大匹配算法看结果是否等于m即可。扩展如果问题变成“最多能完成多少个任务”直接求最大匹配。如果变成“最少需要多少台机器允许机器同时运行多个任务”则是最小点覆盖问题König定理。7.3 例题三有向无环图路径覆盖最小路径覆盖问题给定一个有向无环图求其最小路径覆盖顶点不相交。分析与建模直接套用模型这是最小路径覆盖的经典应用。二分图构建对原图每个顶点i拆成左部点i和右部点i’。连边规则对于原图中的每条有向边 u - v在二分图中连接左部u到右部v’。问题转化求该二分图的最大匹配。答案计算最小路径覆盖数 原图顶点数 - 最大匹配数。输出方案根据二分图匹配结果matchR[v] u我们知道原图中有一条边 u - v 在一条路径上。通过match数组可以还原出每条路径。从所有右部点中未被匹配的点即路径终点开始反向追踪match即可得到所有路径。踩坑点务必注意是有向无环图。如果图中有环这个模型就不适用了因为环无法被一条有向路径覆盖需要至少一个路径起点和终点在环上但拆点后无法表示环。对于有环图需要先求强连通分量进行缩点形成DAG后再应用此模型。8. 实战中的技巧、坑点与经验总结最后分享一些在大量做题后积累的经验这些往往比算法模板本身更重要。1. 如何快速识别二分图问题关键词“匹配”、“覆盖”、“选择”、“互斥”、“冲突”、“交替”、“两类对象”。场景任务分配、人员安排、棋盘覆盖、资源调度、冲突避免。直觉如果你能把问题中的对象分成两组且组内无直接关联关联只存在于组间那很可能就是二分图。2. 建图时顶点规模的估算最坏情况下边数可能达到O(n^2)。如果n达到10^4级别O(n^2)的边数在内存和时间上都无法承受。优化建边利用问题的特殊性质。例如如果左部点只连接右部点的一个连续区间可以用线段树优化建边将边数从O(n^2)降到O(n log n)。3. 匈牙利算法的used数组与HK算法的dist数组这是两个算法正确性的关键也是最容易出错的地方。匈牙利算法的used是每轮DFS独立的标记本轮DFS中尝试过的右部点防止在寻找一条增广路时走回头路。HK算法的dist是全局的在BFS中一次性计算好在DFS中用于指导搜索方向确保找到最短增广路。4. 最大权匹配的算法选择左右部点数相等且求完美匹配优先考虑KM算法O(n^3)对于n500通常可接受。左右部点数不等或不要求完美匹配使用最小费用最大流。建模时注意费用正负求最大权则加负号。边权非负且只需要最大权匹配不一定是最大匹配有时可以转化为最大费用最大流或者使用基于贪心的算法。5. 路径覆盖问题的输出方案得到最大匹配后matchR数组存储了右部点匹配的左部点。matchR[i] j表示原图中有一条边 j - i。所有未被匹配的右部点i即matchR[i] -1是路径的终点。从终点i开始查找matchR[i]得到前驱节点j再找matchR[j]直到找到一个左部点k使得matchR[k] -1这个k就是路径的起点。反向输出即可。6. 多组数据与初始化这是竞赛中最常见的WA原因。务必在每组数据开始时清空邻接表、匹配数组、访问标记等所有数据结构。注意顶点编号是否从0或1开始保持一致。二分图的相关知识体系庞大但结构清晰。从判定到最大匹配再到由König定理串联起来的点覆盖、独立集最后到带权匹配和路径覆盖层层递进。掌握这套工具不仅能解决一大类图论问题更能深刻理解“匹配”这一核心组合优化思想在其他领域的应用。真正的熟练来自于将这些模型内化并在看到新问题时能迅速识别出它背后的二分图骨架。