匈牙利算法求二分图最大匹配 题目描述 给定一个二分图G=(X∪Y, E)，其中X和Y是两个不相交的顶点集合，E是边集。二分图最大匹配问题要求找到包含最多边的匹配M⊆E，其中匹配M是边的集合，且M中任意两条边没有公共顶点。 解题过程 1. 基本概念理解 匹配：边的集合，其中任意两条边不共享顶点 匹配边：属于当前匹配的边 非匹配边：不属于当前匹配的边 饱和点：与匹配边相连的顶点 非饱和点：不与任何匹配边相连的顶点 增广路径：连接两个非饱和点的路径，路径上匹配边和非匹配边交替出现 2. 算法核心思想 匈牙利算法的核心是寻找增广路径。如果存在一条增广路径，我们可以通过"翻转"路径上的边（匹配边变非匹配边，非匹配边变匹配边）来增加匹配的大小。 3. 算法步骤详解 步骤1：初始化 从空匹配开始：M = ∅ 所有顶点最初都是非饱和的 步骤2：为X集合中的每个顶点尝试寻找匹配 遍历X集合中的每个顶点u 如果u已经是饱和点，跳过 如果u是非饱和点，尝试为它寻找匹配 步骤3：寻找增广路径（关键步骤） 使用DFS或BFS从当前顶点u出发寻找增广路径： 从u开始，只能走非匹配边（因为u是非饱和点） 然后只能走匹配边，然后非匹配边...交替进行 目标是找到Y集合中的一个非饱和点 具体DFS过程： 对于当前顶点u∈X，检查它的所有邻接点v∈Y 如果边(u,v)是非匹配边，且v未被访问过： 如果v是非饱和点：找到增广路径！ 如果v是饱和点：从v出发，沿着匹配边走到v的匹配点w∈X，然后递归处理w 步骤4：翻转增广路径 如果找到增广路径u→v₁→u₁→v₂→...→v（其中v是非饱和点）： 将路径上的所有非匹配边加入匹配 将路径上的所有匹配边移出匹配 匹配大小增加1 4. 具体例子演示 考虑二分图：X={1,2,3}, Y={a,b,c} 边集：1-a, 1-b, 2-b, 2-c, 3-a 第一次迭代 （为顶点1寻找匹配）： 从1出发，找到非饱和点a 增广路径：1→a 匹配：{1-a} 第二次迭代 （为顶点2寻找匹配）： 从2出发，尝试边2-b：b是非饱和点 增广路径：2→b 匹配：{1-a, 2-b} 第三次迭代 （为顶点3寻找匹配）： 从3出发，尝试边3-a：a已匹配给1 从a出发，找到匹配边a-1 从1出发，尝试边1-b：b已匹配给2 从b出发，找到匹配边b-2 从2出发，尝试边2-c：c是非饱和点 增广路径：3→a→1→b→2→c 翻转后匹配：{3-a, 1-b, 2-c} 5. 算法实现细节 使用visited数组避免重复访问 使用match数组记录匹配关系 时间复杂度：O(|V|×|E|) 6. 算法正确性证明 关键定理（Berge引理）：匹配M是最大匹配当且仅当图中不存在增广路径。 每次找到增广路径并翻转都会使匹配大小增加1，直到找不到增广路径时达到最大匹配。 7. 应用场景 任务分配问题 婚姻稳定匹配 资源分配优化 棋盘覆盖问题