1. 二分图二分图Bipartite Graph是图论中的一个极其重要且有趣的结构。简单来说如果一个图的顶点可以被分成两个互不相交的独立集合使得图中的每一条边所连接的两个顶点都分别属于这两个不同的集合那么这个图就是一个二分图。你可以把它想象成一个“相亲舞会”男嘉宾是一个集合女嘉宾是另一个集合。所有的连线舞伴关系只能发生在男生和女生之间男生和男生之间、女生和女生之间绝对不会跳舞连线。核心特征与判定定理怎么一眼看出或用代码判断一个图是不是二分图呢这里有一个非常经典的黄金法则核心定理一个图是二分图的充要条件是图中不含有“奇数环”边数为奇数的环。为什么不能有奇环我们来尝试对一个三角形最简单的奇环3条边进行分组假设节点 A 属于集合V1V_1V1​。因为 A 和 B 有边相连所以 B 必须属于集合V2V_2V2​。因为 B 和 C 有边相连所以 C 必须属于集合V1V_1V1​。此时矛盾出现了C 和 A 也有边相连但它们都在V1V_1V1​里这就破坏了二分图的定义。计算机如何判定染色法在算法中我们通常使用DFS深度优先搜索或BFS广度优先搜索配合双色染色法来判定二分图随机选一个未染色的节点染成颜色 1。遍历它的所有邻居将邻居染成颜色 2。继续往下走如果在这个过程中发现某个邻居已经被染了色且颜色和当前节点相同说明图里有奇环直接宣告不是二分图。如果所有节点都能顺利染色且不冲突它就是二分图。二分图的经典核心问题二分图之所以在算法包括运筹学、匹配算法中应用广泛是因为它有一系列衍生出的经典问题1. 二分图的最大匹配Maximum Matching定义在二分图中寻找一个边集使得这个集合中的任意两条边都没有公共端点。换句话说每个点最多只能被一条边匹配。通俗理解舞会上面对众多错综复杂的好感关系主持人最多能同时凑成多少对男女上台跳舞解法经典方法是 匈牙利算法Hungarian Algorithm核心思想是寻找“增广路”不断翻转匹配状态或者转化成网络流问题用 Dinic 算法 解决。2. 二分图的最大完美匹配 / 完备匹配定义如果最大匹配的边数恰好等于其中某个集合的点数即该集合所有点都被匹配了就是完备匹配如果两边所有的点都被匹配了就是完美匹配。3. 带有权重的最大匹配KM 算法通俗理解如果每对男女嘉宾在一起都有一个“幸福指数”边的权重如何匹配才能让整场舞会的总幸福指数最高解法KM 算法Kuhn-Munkres Algorithm或者直接上费用流Min-Cost Max-Flow。三个神奇的等式仅在二分图中成立在二分图中有几个关于“覆盖”与“独立”的性质非常优美面试和算法竞赛常考最大匹配数 最小点覆盖数König定理最小点覆盖选出最少的点使得图中的每条边至少有一个端点被选中就像派最少的保安看守住所有的通道。最大独立集 总点数 - 最大匹配数最大独立集选出最多的点使得这些点之间没有任何边相连互不认识的最大群体。最小路径覆盖针对DAG转化 总点数 - 最大匹配数用最少的互不相交的简单路径覆盖有向无环图的所有顶点。实际应用场景二分图绝不仅存在于教科书里在工业界和实际业务中随处可见它的影子广告推荐 / 用户画像User-Item Graph左边是用户User右边是商品或广告Item。用户点击或购买了商品就连一条边。这是推荐系统最基础的图结构。网约车 / 外卖派单Ride-Hailing Matching左边是乘客订单右边是司机。边代表司机可以在规定时间内接到这个订单边权重可以是距离或预期收益。这就需要通过二分图最大权匹配来做全网最优派单。任务分配Assignment Problem左边是员工右边是工作岗位员工对不同岗位的熟练度不同求解如何分配能让效率最高。2. 匈牙利算法匈牙利算法Hungarian Algorithm是图论中用于解决二分图最大匹配Maximum Matching的经典算法。由匈牙利数学家 Dénes Kőnig 和 Jenő Egerváry 提出后由 James Munkres 完善所以有时也叫 树或路径的增广路算法。它的核心目标是在一个二分图中寻找一个包含边数最多的匹配使得任何两条边都没有公共端点。为了让你秒懂它的核心逻辑我们不需要直接死记硬背枯燥的图论概念而是用最经典的“相亲分配工作”来还原它的执行过程。2.1 核心思想先到先得能让就让增广路匈牙利算法的精髓只有一句话先按顺序给每个人分配如果后面的人遇到了冲突就尝试让前面已经匹配的人“腾出位置”如果能腾出来匹配数就加 1如果无论如何都腾不出来这个人就单着。在算法中这个“腾位置”的调整链条被称为增广路Augmenting Path。2.2 趣味故事算法是如何运行的假设现在有三个男生A, B, C和三个女生X, Y, Z他们的好感关系如下A 喜欢X, YB 喜欢XC 喜欢X, Y我们要撮合尽可能多的人。算法开始按顺序遍历男生第一步轮到 AA 看向自己喜欢的 X发现 X 还没有对象。结果直接配对成功当前组合(A - X)第二步轮到 BB 走向自己唯一喜欢的 X发现 X 已经和 A 在一起了。此时B 不会直接放弃而是发挥匈牙利算法的精髓——去协商找增广路。B 对 A 说“兄弟你能不能把 X 让给我你去看看你别的目标”A 脾气很好看了一下自己的小本本发现自己还喜欢 Y。A 瞅了一眼 Y发现 Y 还是单身。结果A 很大方地把 X 让给了 B自己和 Y 牵手。当前组合调整为 (B - X) 和 (A - Y)。成功多凑出一对第三步轮到 CC 出场他喜欢 X 和 Y但现在 X跟着B和 Y跟着A都有主了。C 决定也去协商。他先找到 XC 对 B 说“B你把 X 让给我吧”B 摇摇头说“兄弟我只喜欢 X我让了她我就彻底单身了没法让。”B 协商失败C 只能去找自己的第二个目标 YC 对 A 说“A你把 Y 让给我吧”A 再次看自己的本本A 喜欢 X 和 Y。A 尝试去找 X“B你能把 X 还给我吗”B 依然拒绝。A 发现自己无路可去只能对 C 说“不行啊兄弟我让了 Y 我就单着了。”A 协商失败结果C 找了一圈发现整个关系网已经锁死没人能挪动位置。C 只能遗憾单身。最终结局成功匹配 2 对(B - X) 和 (A - Y)。这就是该图的最大匹配。2.3. 算法的标准执行步骤DFS / BFS 实现在计算机代码中我们通常用深度优先搜索DFS来实现这个协商过程初始化所有点的匹配状态为空。遍历左边的每一个顶点uuu清空右边顶点的“访问标记数组”每次为新的人找对象时大家都重新参与协商- - 调用 dfs(u) 尝试为uuu寻找匹配。dfs(u) 的内部逻辑遍历uuu所有喜欢的右边顶点vvv如果vvv在这一轮协商中还没被询问过标记vvv已被询问防止死循环。如果vvv当前没有匹配对象或者能够通过 dfs(match[v]) 让vvv的原配对象找到备胎。那么成功将vvv的对象改为uuumatch[v] u并返回 true。如果遍历完所有邻居都无法成功返回 false。2.4. 复杂度分析假设二分图左边有V1V_1V1​个点右边有V2V_2V2​个点总点数VV1V2V V_1 V_2VV1​V2​边数为EEE。时间复杂度算法需要遍历左边的每一个点共V1V_1V1​次每次遍历最坏情况下需要搜遍所有的边EEE。因此最坏时间复杂度为O(V⋅E)O(V \cdot E)O(V⋅E)。空间复杂度需要存储图的邻接表以及匹配状态、访问标记空间复杂度为O(VE)O(V E)O(VE)。2.5. 匈牙利算法的局限与进阶虽然匈牙利算法思路非常清晰、代码极其短小精悍通常20-30行即可写完但它也有局限性处理大规模稀疏图稍慢如果图的规模非常庞大O(V⋅E)O(V \cdot E)O(V⋅E)的复杂度可能会超时。进阶解法Hopcroft-Karp 算法。它通过 BFS 同时寻找多条最短增广路将时间复杂度优化到了O(V⋅E)O(\sqrt{V} \cdot E)O(V​⋅E)。无法处理带权重的边如果每对匹配都有一个“满意度”或“成本”匈牙利算法就无能为力了。进阶解法如果需要求最大权重匹配需要使用 KM 算法Kuhn-Munkres 或转化成费用流MCMF问题来解决。3. KM算法KM 算法Kuhn-Munkres Algorithm也称库恩-克莱斯算法是专门用来解决“二分图最大权完美匹配”的经典算法。如果说匈牙利算法是为了帮更多人“脱单”那 KM 算法就是为了让牵手成功的所有人“总幸福指数最高”。3.1. 核心问题背景假设有NNN个工人和NNN个任务每个工人做不同的任务能产生的效益权重不同。我们希望找到一个一一对应的完整匹配使得所有被匹配的边权之和达到最大。前提条件KM 算法通常假设二分图的两边节点数相同均为NNN且存在完美匹配如果初始图不是完美匹配可以通过补全节点、将不存在的边权重设为 0 来转化。3.2. 核心思想从“可行顶标”到“相等子图”KM 算法精妙的地方在于它把一个带权重的最优化问题通过一种叫顶标Vertex Label的机制转化成了无权重的匈牙利算法问题。它为每个节点引入了一个小账本标号左边工人的每个点iii有一个期望值顶标记为lx[i]lx[i]lx[i]右边任务的每个点jjj有一个期望值顶标记为ly[j]ly[j]ly[j]在整个算法运行过程中必须始终满足一个铁律——可行顶标性质lx[i]ly[j]≥weight(i,j)lx[i] ly[j] \ge weight(i, j)lx[i]ly[j]≥weight(i,j)通俗理解工人的心理预期 任务的心理预期≥\ge≥两人实际能创造的价值。什么是“相等子图”如果某条边正好满足lx[i]ly[j]weight(i,j)lx[i] ly[j] weight(i, j)lx[i]ly[j]weight(i,j)这意味着这条边完美达到了两边的预期。我们把所有满足这个等式的边挑出来连成一个新的图叫做相等子图。KM 算法的黄金定理如果相等子图中存在完美匹配那么这个匹配就是原图的最大权完美匹配。证明直觉因为每一条边的实际权重都等于两个顶标之和完美匹配的总权重就等于所有节点的顶标总和。而根据铁律任何其他匹配的边权和都不可能超过顶标总和。因此当前这个匹配一定是最优的。3.3. 算法执行流程怎么跑起来的KM 算法的核心逻辑就是通过不断调整顶标来扩大相等子图直到在相等子图中找到完美匹配。步骤一初始化顶标让左边的工人期望值拉满lx[i]max⁡j{weight(i,j)}lx[i] \max_{j} \{ weight(i, j) \}lx[i]maxj​{weight(i,j)}每个工人初始都想挑对自己价值最高的任务。让右边的任务期望值降到最低ly[j]0ly[j] 0ly[j]0。显然此时满足lx[i]ly[j]≥weight(i,j)lx[i] ly[j] \ge weight(i, j)lx[i]ly[j]≥weight(i,j)。步骤二用匈牙利算法尝试匹配只看相等子图中的边用标准的匈牙利算法为每个工人找任务。如果所有工人顺利匹配成功算法结束。步骤三匹配卡住降低期望调整顶标如果某个工人iii找不到匹配遇到了冲突且没办法腾出位置说明当前的相等子图“太瘦了”需要放宽条件把更多的边纳入相等子图。怎么调整顶标才能既引入新边又不破坏铁律呢在匈牙利算法深度搜索的过程中会形成一棵交错树包含所有参与了这次冲突讨论的左边点集SSS和右边点集TTT。寻找那些左边在SSS中右边不在TTT中的边计算它们离加入相等子图还差多少dmin⁡{lx[i]ly[j]−weight(i,j)}(i∈S,j∉T)d \min \{ lx[i] ly[j] - weight(i, j) \} \quad (i \in S, j \notin T)dmin{lx[i]ly[j]−weight(i,j)}(i∈S,j∈/T)更新顶标所有在交错树中的左边节点期望调低lx[i]lx[i]−dlx[i] lx[i] - dlx[i]lx[i]−d所有在交错树中的右边节点期望调高ly[j]ly[j]dly[j] ly[j] dly[j]ly[j]d这步调整的妙处对于已经在交错树里的边lxlxlx减了dddlylyly加了ddd和保持不变它们依然留在相等子图里对于左边在树里、右边在树外的边lxlxlx减了dddlylyly没变它们的值逼近了边权。由于ddd是取最小差距至少会有一条新边满足lx[i]ly[j]weight(i,j)lx[i] ly[j] weight(i, j)lx[i]ly[j]weight(i,j)从而被拉入相等子图。步骤四重复循环重复步骤二和三直到所有点都匹配上。3.4. 复杂度与现代优化传统实现如果每次调整顶标都去遍历所有边寻找最小的ddd调整一次需要O(N2)O(N^2)O(N2)总共可能调整O(N)O(N)O(N)次配合匈牙利算法的O(N)O(N)O(N)搜索整体复杂度是O(N4)O(N^4)O(N4)。Slack 数组优化在搜索过程中为右边的每个点维护一个 slack[j] 数组记录它距离进入相等子图的最小差距。这样寻找ddd的时间降到O(N)O(N)O(N)整体算法复杂度可以优化到O(N3)O(N^3)O(N3)。3.5 KM 算法 vs 费用流在实际工程比如网约车派单系统、广告竞价匹配中如果遇到类似的问题往往有两种选择特性KM 算法最小费用最大流 (MCMF)适用场景稠密二分图、完美的 1对1 匹配稀疏图、复杂的流量限制、多对多匹配时间复杂度O(N3)O(N^3)O(N3)在稠密图上常数极小速度极快依赖于流大小和算法实现如 SPFA/Dijkstra通常稍慢实现难度代码短小精悍100行以内需要构建复杂的源点、汇点和反向边总结如果面对的是纯粹的、规模在几百到几千的二分图 1对1 最大权匹配优化后的 KM 算法是性能之王但如果业务逻辑变得复杂例如一个司机可以顺路接两个订单就需要全面转向网络流或运筹学求解器如 Gurobi了。