二分图匈牙利算法KM算法

1. 二分图

二分图（Bipartite Graph）是图论中的一个极其重要且有趣的结构。简单来说，如果一个图的顶点可以被分成两个互不相交的独立集合，使得图中的每一条边所连接的两个顶点都分别属于这两个不同的集合，那么这个图就是一个二分图。

你可以把它想象成一个“相亲舞会”：男嘉宾是一个集合，女嘉宾是另一个集合。所有的连线（舞伴关系）只能发生在男生和女生之间，男生和男生之间、女生和女生之间绝对不会跳舞（连线）。

核心特征与判定定理

怎么一眼看出或用代码判断一个图是不是二分图呢？这里有一个非常经典的黄金法则：

核心定理：一个图是二分图的充要条件是，图中不含有“奇数环”（边数为奇数的环）。

为什么不能有奇环？

我们来尝试对一个三角形（最简单的奇环，3条边）进行分组：

1. 假设节点 A 属于集合V1V_1V1​。
2. 因为 A 和 B 有边相连，所以 B 必须属于集合V2V_2V2​。
3. 因为 B 和 C 有边相连，所以 C 必须属于集合V1V_1V1​。
4. 此时矛盾出现了：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, Y
• B 喜欢：X
• C 喜欢：X, Y

我们要撮合尽可能多的人。算法开始按顺序遍历男生：

第一步：轮到 A

• A 看向自己喜欢的 X，发现 X 还没有对象。
• 结果：直接配对成功！当前组合：(A - X)

第二步：轮到 B

• B 走向自己唯一喜欢的 X，发现 X 已经和 A 在一起了。
• 此时，B 不会直接放弃，而是发挥匈牙利算法的精髓——去协商（找增广路）。
• B 对 A 说：“兄弟，你能不能把 X 让给我，你去看看你别的目标？”
• A 脾气很好，看了一下自己的小本本，发现自己还喜欢 Y。A 瞅了一眼 Y，发现 Y 还是单身。
• 结果：A 很大方地把 X 让给了 B，自己和 Y 牵手。
• 当前组合：调整为 (B - X) 和 (A - Y)。成功多凑出一对！

第三步：轮到 C

• C 出场，他喜欢 X 和 Y，但现在 X（跟着B）和 Y（跟着A）都有主了。
• C 决定也去协商。他先找到 X：
  • C 对 B 说：“B，你把 X 让给我吧？”
  • B 摇摇头说：“兄弟，我只喜欢 X，我让了她我就彻底单身了，没法让。”（B 协商失败）
• C 只能去找自己的第二个目标 Y：
  • C 对 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的对象改为uuu（match[v] = u），并返回 true。
  • 如果遍历完所有邻居都无法成功，返回 false。

2.4. 复杂度分析

假设二分图左边有V1V_1V1​个点，右边有V2V_2V2​个点（总点数V=V1+V2V = V_1 + V_2V=V1​+V2​），边数为EEE。

• 时间复杂度：算法需要遍历左边的每一个点（共V1V_1V1​次），每次遍历最坏情况下需要搜遍所有的边（EEE）。因此，最坏时间复杂度为O(V⋅E)O(V \cdot E)O(V⋅E)。
• 空间复杂度：需要存储图的邻接表以及匹配状态、访问标记，空间复杂度为O(V+E)O(V + E)O(V+E)。

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找不到匹配（遇到了冲突，且没办法腾出位置），说明当前的相等子图“太瘦了”，需要放宽条件，把更多的边纳入相等子图。

怎么调整顶标才能既引入新边，又不破坏铁律呢？

1. 在匈牙利算法深度搜索的过程中，会形成一棵交错树（包含所有参与了这次冲突讨论的左边点集SSS和右边点集TTT）。
2. 寻找那些左边在SSS中，右边不在TTT中的边，计算它们离加入相等子图还差多少：

d=min⁡{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)d=min{lx[i]+ly[j]−weight(i,j)}(i∈S,j∈/T)

3. 更新顶标：

• 所有在交错树中的左边节点，期望调低：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减了ddd，lylyly加了ddd，和保持不变，它们依然留在相等子图里！
• 对于左边在树里、右边在树外的边，lxlxlx减了ddd，lylyly没变，它们的值逼近了边权。由于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 费用流

在实际工程（比如网约车派单系统、广告竞价匹配）中，如果遇到类似的问题，往往有两种选择：

总结：如果面对的是纯粹的、规模在几百到几千的二分图 1对1 最大权匹配，优化后的 KM 算法是性能之王；但如果业务逻辑变得复杂（例如：一个司机可以顺路接两个订单），就需要全面转向网络流或运筹学求解器（如 Gurobi）了。