二分图的最大匹配问题（匈牙利算法） 题目描述 给定一个二分图，其顶点集被划分为两个不相交的子集（通常称为“左部”和“右部”），且图中每条边连接一个左部顶点和一个右部顶点。求该二分图的 最大匹配 ，即找到一个包含尽可能多边的子集，使得任意两条边没有公共顶点。 例如，左部顶点集为 {A, B, C}，右部顶点集为 {1, 2, 3}，边集为 {(A,1), (A,2), (B,2), (B,3), (C,1)}。最大匹配可以是 {(A,1), (B,3), (C,2)}（需通过算法验证是否最优）。 解题思路：匈牙利算法 核心思想：通过不断寻找“增广路径”来扩大匹配。 匹配边 ：当前匹配中包含的边。 未匹配边 ：当前匹配中未包含的边。 增广路径 ：一条起点和终点均为未匹配顶点的路径，且路径中匹配边和未匹配边交替出现。性质：将增广路径上的边状态取反（匹配变未匹配，未匹配变匹配），匹配数会增加 1。 步骤详解 初始化 匹配字典 match ：记录右部顶点当前匹配的左部顶点（无匹配则为 None ）。 例如： match[1] = A 表示右部顶点 1 与左部顶点 A 匹配。 遍历每个左部顶点 对每个左部顶点 u ，尝试为它寻找匹配的右部顶点： 使用深度优先搜索（DFS）或广度优先搜索（BFS）寻找从 u 出发的增广路径。 搜索过程中需标记已访问的顶点，避免重复搜索。 DFS 寻找增广路径 对于当前左部顶点 u ，遍历其所有邻接的右部顶点 v ： 若 v 在当前轮次未被访问过，则标记为已访问。 情况 1： v 未匹配 → 直接匹配 u 和 v ，找到增广路径。 情况 2： v 已匹配某个左部顶点 u' → 递归检查能否为 u' 找到新的匹配（即从 u' 出发重新搜索增广路径）。若成功，则腾出 v 给 u 。 若所有邻接点均失败，则 u 暂时无法匹配。 更新匹配 每当找到一条增广路径，沿路径反转边的状态（匹配↔未匹配），匹配数 +1。 示例演示 图：左部 {A, B, C}，右部 {1, 2, 3}，边集 A-1, A-2, B-2, B-3, C-1。 初始匹配为空。 处理 A ： 尝试匹配 A-1（1 未匹配）→ 匹配成功： match[1]=A 。 处理 B ： 尝试 B-2（2 未匹配）→ 匹配成功： match[2]=B 。 处理 C ： 尝试 C-1（1 已匹配 A）→ 递归检查 A 能否换到其他点： A 的邻接点有 {1, 2}，但 1 已被访问，尝试 2（2 匹配 B）→ 递归检查 B 能否换匹配： B 的邻接点 {2, 3}，2 已被访问，尝试 3（3 未匹配）→ B 匹配 3 成功。 于是 A 可匹配 2，释放 1 给 C。 最终匹配：A-2, B-3, C-1。 复杂度分析 最坏情况：遍历所有左部顶点（O(V)），每个顶点可能遍历所有边（O(E)），总复杂度 O(V·E) 。 实际效率较高，适用于稀疏图。 关键点总结 匈牙利算法的核心是 反复寻找增广路径 。 每次成功找到增广路径，匹配数增加 1。 当无法找到增广路径时，达到最大匹配。