二分图最大匹配的匈牙利算法

题目描述：给定一个二分图，包含两个不相交的顶点集U和V，以及连接U和V的边集E。二分图最大匹配问题要求找到最大的边集合M⊆E，使得M中任意两条边都不共享公共顶点。

解题过程：

1. 基本概念理解

• 匹配：边的集合，其中任意两条边不共享顶点
• 最大匹配：包含边数最多的匹配
• 增广路径：从未匹配点出发，交替经过匹配边和非匹配边，最终到达另一个未匹配点的路径
• 关键定理：一个匹配是最大匹配当且仅当不存在增广路径

2. 算法核心思想
   匈牙利算法通过不断寻找增广路径来扩大匹配：

• 初始时匹配为空
• 每次尝试为U集中的顶点寻找匹配
• 如果找到增广路径，就通过"取反"操作（匹配边变非匹配边，非匹配边变匹配边）来增加匹配数

3. 详细步骤

步骤1：初始化

• 创建匹配数组match[]，记录每个V顶点匹配的U顶点（初始为-1）
• 创建访问数组visited[]，用于DFS过程中的标记

步骤2：主循环
对U集中的每个顶点u执行：

• 重置visited数组
• 调用DFS(u)尝试为u寻找匹配

步骤3：DFS函数（递归搜索）
function dfs(u):
for 每个与u相邻的顶点v in V:
if v未被访问过:
标记v为已访问
if v未匹配 或 与v匹配的u'可以找到新的匹配:
将u与v匹配
返回匹配成功
返回匹配失败

4. 具体例子演示
   考虑二分图：U={1,2,3}, V={4,5,6}
   边集：1-4,1-5,2-5,2-6,3-4

迭代过程：

• 顶点1：匹配1-4
• 顶点2：尝试匹配2-5，成功
• 顶点3：尝试匹配3-4
  • 4已匹配给1，尝试为1重新匹配
  • 1可以匹配5，但5已匹配给2，尝试为2重新匹配
  • 2可以匹配6，成功
  • 回溯：2匹配6，1匹配5，3匹配4
    最终得到最大匹配：1-5, 2-6, 3-4

5. 算法复杂度分析

• 时间复杂度：O(|E|×|U|)
• 空间复杂度：O(|U|+|V|+|E|)

6. 优化技巧

• 使用BFS代替DFS可以减少递归深度
• 预处理时可以先尝试贪心匹配
• 对于稀疏图，使用邻接表存储提高效率

该算法通过系统性地搜索增广路径，确保找到最大匹配，是解决二分图匹配问题的经典方法。