1. 项目概述为什么二分图值得你花时间彻底搞懂如果你刷过一些算法题或者接触过图论相关的项目大概率见过“二分图”这个词。它可能出现在“判断是否为二分图”的简单题里也可能藏在“最大匹配”、“最小点覆盖”这些听起来就有点复杂的题目背后。很多人对它的印象停留在“一种特殊的图”知道用染色法判断再深一点可能就是匈牙利算法但往往也就到此为止了。实际上二分图远不止一个算法知识点它是一套非常强大的建模工具能把许多看似复杂、毫不相干的问题转化成一个清晰、可解的图论模型。我自己最初学二分图时也是懵懵懂懂直到后来在解决一个实际的资源调度问题时才真正体会到它的威力。那个问题描述起来很绕有几项任务和几个执行单元每个任务只能由特定的几个单元来完成每个单元同时只能处理一个任务如何安排能让完成的任务数最多乍一看需要复杂的逻辑判断但把它抽象成二分图——一边是任务节点一边是单元节点能执行就在中间连一条边——问题瞬间变成了求二分图的“最大匹配”。用匈牙利算法跑一遍方案就出来了。这种“化繁为简”的体验让我意识到掌握二分图的核心不是背模板而是理解其建模思想。所以这篇内容的目的不是罗列概念和代码而是帮你搭建一个关于二分图的完整认知框架。我们会从“它到底是什么”开始拆解染色法和匈牙利算法背后的每一个为什么然后深入到最大匹配、最小点覆盖这些核心概念的联系最后看看这些理论如何落地到具体的题目和应用场景中。无论你是正在准备算法面试还是希望提升解决实际问题的建模能力相信这套整理都能给你带来实实在在的收获。2. 二分图的核心概念与判定方法2.1 二分图的本质一种基于分类的约束关系模型给二分图下个形式化的定义很简单对于一个无向图 G(V, E)如果能把顶点集 V 分成两个互不相交的子集 A 和 B使得图中的每一条边 (u, v) 都满足 u 属于 A 且 v 属于 B或者相反那么 G 就是一个二分图。子集 A 和 B 通常被称为图的两部或两个“集合”。这个定义听起来有点学术我们可以换个方式理解二分图描述的是两种不同类型事物之间的一种“匹配”或“关联”关系。这两种事物各自内部是没有直接关联的集合内部无边所有的关系都发生在两种不同事物之间集合之间有边。生活中有大量符合二分图模型的例子求职市场求职者一部和招聘岗位另一部。一个求职者可以投递多个岗位一个岗位也可以收到多份简历但求职者之间、岗位之间没有直接的“应聘”关系。电影推荐用户一部和电影另一部。用户可以对电影评分这条评分边就连接了用户和电影。社交网络中的关注关系在某些特定平台例如一个平台只有“博主”和“粉丝”两种角色那么“关注”关系只能从粉丝节点指向博主节点这也构成了一个二分图更准确地说是有向二分图。理解二分图的核心在于抓住“二分”这个词。它意味着顶点可以被划分到两个阵营并且所有连接都必须是“跨阵营”的。这种结构上的限制恰恰是许多算法能够高效工作的前提。2.2 染色法如何判断一个图是不是二分图给定一个任意的图我们如何判断它是否满足二分图的定义呢这就是染色法要解决的问题。其核心思想非常直观尝试用两种颜色对图中的所有顶点进行着色要求任意一条边两端的顶点颜色都不能相同。如果能用两种颜色完成符合要求的着色那么这个图就是二分图否则就不是。为什么两种颜色就够了这正好对应了二分图的两部。我们可以把一种颜色的顶点归为集合 A另一种颜色的顶点归为集合 B。着色过程本质上就是在模拟和验证二分图的划分过程。2.2.1 染色法的详细步骤与代码实现染色法通常使用深度优先搜索DFS或广度优先搜索BFS来实现。我更推荐使用 DFS因为思路更清晰递归的写法能很好地体现“尝试着色-检查冲突-回溯或继续”的过程。下面以 DFS 为例拆解每一步初始化创建一个颜色数组color[]长度等于顶点数初始值设为“未着色”例如用 0 表示。同时假设图以邻接表形式存储。遍历顶点因为图可能不连通我们需要对每个未着色的顶点启动一次 DFS确保所有连通分量都被检查到。DFS 着色过程对于当前顶点u将其着上一种颜色例如 1。遍历u的所有邻居顶点v如果v未着色则递归地对v进行着色颜色与u相反例如u是 1则v尝试着 2。如果递归调用返回 false表示子图着色失败则整个图不是二分图。如果v已着色则检查v的颜色是否与u的颜色不同。如果相同则发现冲突立即返回 false。返回结果如果所有 DFS 遍历都顺利完成没有发现冲突则说明整个图可以二着色即是二分图。#include vector using namespace std; bool isBipartiteDFS(int u, int c, vectorint color, const vectorvectorint graph) { color[u] c; // 将当前节点u染成颜色c for (int v : graph[u]) { // 遍历u的所有邻居v if (color[v] 0) { // 如果邻居v未染色 // 递归染相反颜色如果失败则返回false if (!isBipartiteDFS(v, 3 - c, color, graph)) { return false; } } else if (color[v] c) { // 如果邻居v已染色且颜色与u相同 return false; // 冲突不是二分图 } } return true; // 当前连通分量染色成功 } bool isBipartite(int n, const vectorvectorint graph) { vectorint color(n, 0); // 0表示未染色1和2表示两种颜色 for (int i 0; i n; i) { if (color[i] 0) { // 对每个未染色的连通分量启动DFS if (!isBipartiteDFS(i, 1, color, graph)) { return false; } } } return true; }2.2.2 注意事项与常见错误图可能不连通这是最容易忽略的一点。只从节点 0 开始一次 DFS 是不够的必须循环检查所有节点确保每个连通分量都被验证。颜色表示使用 1 和 2或者 1 和 -1 都很方便。代码中3 - c是一种巧妙的取反方式当c1时3-12当c2时3-21。时间复杂度染色法需要遍历所有的顶点和边因此时间复杂度是 O(V E)其中 V 是顶点数E 是边数。这对于大多数情况都是非常高效的。BFS实现BFS版本的思路类似使用队列。从某个未着色点开始将其着色后入队。然后每次从队列取出一个节点检查其所有邻居的着色情况。逻辑和DFS一致只是遍历顺序不同。注意染色法判断的是无向图是否是二分图。对于有向图通常需要忽略方向将其视为无向图来进行判断因为二分图的定义基于无向边。3. 二分图匹配的核心匈牙利算法详解当我们确认一个图是二分图后最经典的问题之一就是求它的最大匹配。匹配是指一组边的集合其中任意两条边都没有公共顶点。最大匹配就是所有匹配中边数最多的那个。匈牙利算法Hungarian Algorithm是解决二分图最大匹配问题最常用、最经典的算法之一其核心思想是通过寻找“增广路径”来不断增加匹配数。3.1 增广路径算法的心脏理解匈牙利算法的关键在于理解增广路径。定义如下在当前的匹配方案下一条从非匹配点出发依次经过非匹配边、匹配边、非匹配边、匹配边……最后到达另一个非匹配点的路径。增广路径有什么特点路径的起点和终点都是目前还没有配对的点非匹配点。路径上的边是“非匹配边”和“匹配边”交替出现的。因为起点和终点都是非匹配点所以路径上的非匹配边比匹配边多一条。算法的魔法就发生在对增广路径的操作上我们把增广路径上的所有边的状态“反转”——原来的匹配边变成非匹配边原来的非匹配边变成匹配边。操作之后路径两端的非匹配点都变成了匹配点。路径中间的匹配点依然保持匹配只是换了对象。总的匹配边数增加了一条。这就好比一条绳子原来有些段打了结匹配边有些段没打结非匹配边。现在我们从两头没打结的地方开始把整条绳子的打结状态全部反过来结果两头都打上了结总结数就多了一个。匈牙利算法就是不断地在图中寻找这样的“增广路径”然后进行“反转”操作直到再也找不到任何增广路径为止。根据相关定理此时得到的匹配就是最大匹配。3.2 匈牙利算法的执行流程与代码实现假设二分图的两部分别为集合 U 和 V。算法通常从 U 集合出发尝试为其中的每一个节点寻找匹配。初始化记录 V 集合中每个节点的匹配对象match[v]初始化为“无匹配”例如 -1。遍历 U 集合依次尝试为 U 中的每个节点u寻找增广路径。为单个 u 寻找增广路径DFS函数为了在搜索中避免重复访问需要一个visited数组记录本次搜索中 V 集合的节点是否被查询过。遍历u的所有邻居v。如果v在本轮搜索中未被访问过则标记访问。然后检查v的状态如果v还没有匹配match[v] -1那么直接让u匹配v找到一条增广路径返回成功。如果v已经有匹配对象match[v]那么就“递归地”尝试为match[v]这是 U 集合中的另一个点寻找新的匹配。如果能为match[v]找到新的匹配即存在一条从match[v]出发的增广路径那么v就可以“让出来”给u从而为u找到匹配。如果所有邻居都尝试失败则说明从当前u出发无法找到增广路径。统计结果累计每次成功为u找到匹配的次数即为最大匹配数。#include vector using namespace std; class Hungarian { private: vectorvectorint graph; // 邻接表graph[u] 存储u的所有邻居v vectorint matchV; // 记录V集合中每个点的匹配对象来自U vectorbool used; // 记录V集合中的点在单轮DFS中是否被访问过 bool dfs(int u) { for (int v : graph[u]) { if (!used[v]) { // 如果v在本轮DFS中还未被尝试 used[v] true; // 如果v未被匹配或者能为v的原配对象找到新匹配 if (matchV[v] -1 || dfs(matchV[v])) { matchV[v] u; // 匹配成功 return true; } } } return false; // 尝试所有邻居后失败 } public: Hungarian(const vectorvectorint g) : graph(g) {} int maxMatching(int nU, int nV) { // nU: U集合大小 nV: V集合大小 matchV.assign(nV, -1); int result 0; for (int u 0; u nU; u) { used.assign(nV, false); // 每轮DFS初始化访问标记 if (dfs(u)) { result; } } return result; } };3.2.1 算法复杂度与实操要点时间复杂度最坏情况下需要为 U 中每个点遍历所有边因此复杂度为 O(U * E)。这在 U 和 E 规模不大通常几百到几千时效率很高也是其被广泛使用的原因。used数组的重置used数组记录的是在为当前u寻找匹配的这轮 DFS中V 集合的点是否被访问过。它的作用是防止在递归寻找增广路径时陷入死循环。必须在为每一个新的u启动 DFS 前将used数组重置为全 false。递归的理解dfs(matchV[v])是算法的精髓。它意味着“尝试让 v 的原配对象matchV[v]去找别的对象从而把 v 空出来”。这是一个递归的“协商”过程。3.3 从最大匹配到最小点覆盖König定理这是二分图理论中一个非常优美且实用的定理。点覆盖是指图中的一个顶点集合使得图中的每一条边都至少有一个端点属于这个集合。最小点覆盖就是点数最少的点覆盖。König 定理指出在二分图中最大匹配的边数等于最小点覆盖的点数。这个定理为什么重要因为它建立了一个看似困难的问题最小点覆盖是 NP-Hard 问题和一个已解决问题最大匹配之间的桥梁。我们不需要去直接求解最小点覆盖只需要用匈牙利算法求出最大匹配数这个数就是最小点覆盖所需的点数。如何构造出一个具体的最小点覆盖点集算法步骤如下基于匈牙利算法结束后的状态从 U 集合中所有未匹配点出发进行交替路遍历只能走未匹配点-未匹配边-匹配点-匹配边-……。标记所有在遍历过程中访问到的点。构造覆盖集取U 集合中未被标记的点加上V 集合中被标记的点。这个集合就是一个最小点覆盖。这个构造方法的理解需要结合增广路径和覆盖的定义记住结论并在需要时能复现步骤即可。在解决“最少需要选择哪些点来覆盖所有边”这类问题时这个定理和构造法能直接给出答案。4. 二分图相关算法的进阶概念与应用掌握了判定和最大匹配二分图的世界才刚刚打开大门。围绕匹配衍生出了一系列重要的概念和问题它们彼此关联构成了一个丰富的知识体系。4.1 最大匹配的变体与相关概念完美匹配如果匹配 M 覆盖了图中的所有顶点即每个顶点都是匹配点那么 M 称为完美匹配。显然完美匹配是最大匹配但最大匹配不一定是完美匹配。完美匹配要求图的两部顶点数相同。最大权匹配如果二分图的边上带有权重那么最大权匹配的目标是找到一个匹配使得所有匹配边的权重之和最大。这不再是匈牙利算法的范畴通常使用KM 算法Kuhn-Munkres算法或转化为最小费用最大流问题来解决。KM 算法能在 O(n^3) 时间内解决带权二分图的最优匹配问题例如在任务分配中考虑效率和成本时非常有用。多重匹配即一个点可以匹配多个点但有其上限。例如一个老师可以辅导多个学生但最多辅导 3 个。这类问题通常可以通过拆点转化为普通的最大匹配问题将容量为 c 的点拆成 c 个独立的点或者直接使用网络流模型来求解。4.2 二分图建模的经典问题范式二分图算法的威力在于建模。以下是一些经典范式看到类似问题可以立刻联想到二分图行列模型这是最直接的模型。当问题中天然存在两种类型的对象且关系只存在于不同类型对象之间时直接建模。例题棋盘覆盖问题。一个棋盘上有一些障碍问最多能放多少个1x2的骨牌不重叠且不覆盖障碍。可以将棋盘黑白染色黑色格子和白色格子构成二分图的两部相邻格子连边问题转化为求此二分图的最大匹配。“冲突”或“互斥”关系模型如果问题描述为某些元素不能共存往往可以转化为二分图。不能共存的两个元素连一条边那么问题可能就变成了在图中寻找最大的、内部没有边的点集独立集而二分图的最大独立集大小 顶点总数 - 最小点覆盖数。例题学生选课冲突。有些课程时间冲突不能同时选。将课程作为顶点冲突课程间连边。如果冲突关系构成二分图即课程可以分成两组组内无冲突那么求最多能选多少门不冲突的课就是求二分图的最大独立集。“覆盖”模型要求用最少的“资源”覆盖所有“目标”。这直接对应最小点覆盖问题。例题监控布置。在一个街道网格中每个监控可以覆盖其所在位置的行和列。问最少需要多少个监控才能覆盖所有关键点。将关键点的行号和列号分别作为二分图的两部每个关键点对应一条连接其行和列的边。那么覆盖所有关键点边所需的最少监控数就是覆盖所有这些边所需的最少行或列数即该二分图的最小点覆盖。4.3 二分图与网络流的联系二分图匹配问题可以看作是网络流问题的一个特例。我们可以这样构建一个流网络增加一个超级源点s连接所有 U 集合中的点容量为 1。增加一个超级汇点t所有 V 集合中的点连接t容量为 1。将原二分图中的边 (u, v) 改为从 u 指向 v 的有向边容量为 1。在这个网络中从s到t的最大流的值就等于原二分图的最大匹配数。每条流量为 1 的s - u - v - t的路径就对应了一个匹配 (u, v)。为什么要了解这个联系统一视角网络流是一个更通用的框架二分图匹配是其子问题。理解联系有助于融会贯通。解决更复杂问题当匹配问题出现变体如多重匹配、带权匹配时直接使用最大流或最小费用最大流模型可能比改造匈牙利/KM算法更直观、更方便。工具选择对于简单的二分图最大匹配匈牙利算法编码更简单、常数更小。但对于复杂的匹配问题直接套用网络流模板可能是更稳妥的选择。5. 实战应用与题目解析理论需要结合实践。下面我们通过几道典型的题目来看看如何将具体问题抽象成二分图模型并选择合适的算法解决。5.1 题目一判断二分图LeetCode 785这是最基础的入门题直接检验染色法的掌握程度。题目描述给定一个无向图判断它是否是二分图。建模与求解 这就是染色法的直接应用。图以邻接表形式给出我们只需要实现标准的 DFS 或 BFS 染色流程即可。注意处理图不连通的情况。关键点使用color数组0/1/2 三种状态。递归函数中如果发现邻居已染色且颜色相同立即返回 false。主函数中循环检查所有节点确保每个连通分量都被处理。这道题是后续所有二分图问题的基础必须熟练掌握。5.2 题目二课程表 II 的二分图匹配视角LeetCode 210 变体思考原课程表 II 是拓扑排序问题。但我们考虑一个变体假设有numCourses门课程记为C1, C2, ...。有m位老师每位老师只能教授其擅长列表中的课程且一位老师在同一时间段只能教一门课。问是否存在一种安排使得所有课程都能被有资质的老师教授建模 这显然是一个二分图匹配问题。一部是老师T另一部是课程C。如果老师t_i擅长课程c_j则在它们之间连一条边。我们需要判断是否存在一个匹配能够覆盖所有的课程即课程集合的每个点都是匹配点。这被称为“完全匹配”或“完美匹配”当老师数与课程数相同时。求解 调用匈牙利算法计算最大匹配数。如果最大匹配数等于课程数量numCourses则说明存在这样的安排。我们甚至可以通过matchV数组回溯出具体的匹配方案哪位老师教哪门课。与网络流的关联 如果加上更多限制比如老师有授课时间上限多重匹配或者每门课有不同的优先级带权匹配问题就会变得更复杂。这时将其转化为网络流问题会更方便源点 - 老师容量为老师的授课门数上限。老师 - 课程容量为 1表示一次匹配。课程 - 汇点容量为 1每门课只需一位老师。 求此网络的最大流若最大流等于课程总数则安排可行。5.3 题目三消灭怪物的最少天数LeetCode 1928 类比建模这是一道难度较高的题目但核心思想可以用二分图的最小点覆盖来类比理解。我们看一个简化描述你有一个武器数组每个武器每天可以消灭特定类型的怪物。怪物每天都会出现你必须保证每天出现的所有怪物类型都至少有一种武器能对付。问最少使用这些武器多少天每天可以选择使用武器的子集可以应对接下来 n 天里每天出现的怪物类型集合。思路类比并非原题直接解 我们可以构造一个二分图一部是“武器” (W)。另一部是“天” (D)。如果武器w_i在第d_j天能消灭当天出现的所有怪物类型即武器能力集合包含当天怪物类型集合则在w_i和d_j之间连一条边。一条边表示“这把武器可以在这一天负责”。现在我们需要选择一个武器的子集对应选择二分图中一些W点使得这些武器能够覆盖所有的天即所有的D点都与至少一个被选中的W点相连。这看起来像一个“覆盖”问题。实际上如果我们求这个二分图的最小点覆盖得到的是最少的点武器点或天点来覆盖所有边。但我们的目标是覆盖所有“天”点这是一个“支配集”问题选一些点使得图中所有点要么被选要么与被选点相邻。在二分图中对一部点如天点D的支配集问题可以转化为对另一部点武器点W的最小点覆盖问题吗需要具体分析。原题更复杂涉及每天的选择和状态的延续性。但这个类比说明了当遇到“选择最少的 X 来覆盖/控制所有的 Y”这类问题时二分图的最小点覆盖或支配集模型是一个强有力的思考方向。实际解题可能需结合动态规划或状态压缩但二分图的建模思想提供了清晰的切入点。5.4 避坑指南与性能优化在实际编码和解题中有一些常见的坑点和优化技巧邻接表存储对于稀疏图二分图通常是稀疏的因为边只存在于两部之间务必使用邻接表vectorvectorint而非邻接矩阵否则在顶点数多时会浪费大量空间和时间。匈牙利算法的递归深度DFS 实现的匈牙利算法在极端情况下如链式图递归深度可能等于顶点数有可能导致栈溢出。如果顶点数上万可以考虑使用 BFS 实现的匈牙利算法即 Hopcroft-Karp 算法或者手动设置栈大小。Hopcroft-Karp 算法能在 O(sqrt(V) * E) 的时间内求解对于大规模二分图效率更高。used数组的优化在一些特定场景下可以用时间戳来替代每次重置used数组。我们用一个vis数组和全局时间戳clock。每次 DFS 开始时clock访问节点v时标记vis[v] clock。判断是否访问过只需看vis[v] clock。这避免了频繁重置数组的开销。明确集合划分有时题目不会明确给出两个集合。你需要自己定义什么是“左部”什么是“右部”。通常将主动发起匹配的一方如求职者、任务作为左部 U在匈牙利算法中主动进行 DFS 遍历。匹配方案的输出匈牙利算法结束后matchV[v]数组存储了最大匹配方案。matchV[v] u表示右部点 v 匹配了左部点 u。如果需要输出具体方案遍历matchV数组即可。注意matchV中值为 -1 的点是未匹配的右部点而左部点中未匹配的点没有直接记录需要通过检查所有左部点 u 是否存在于某个matchV[v]的值中来推断。二分图的掌握是一个从“识记算法”到“理解模型”再到“灵活应用”的过程。最初的几步可能只是记住染色法和匈牙利算法的模板但当你开始有意识地将问题中的“两类事物”和“它们之间的关系”抽象出来时你就真正拥有了用二分图这把利器去剖析复杂问题的能力。多练习相关的题目尝试用二分图的视角去重新审视问题这种建模思维会逐渐成为你的本能反应。