二分图的最大匹配问题（匈牙利算法）

题目描述
给定一个二分图G=(U,V,E)，其中U和V是两个不相交的顶点集合，E是连接U和V的边集合。匹配是指一组没有公共顶点的边集合。最大匹配是指包含边数最多的匹配。请设计算法找出该二分图的最大匹配。

基本概念解析

1. 二分图：顶点可被划分为两个不相交集合U和V，所有边都连接U和V中的顶点
2. 匹配：边的集合，其中任意两条边没有公共顶点
3. 最大匹配：包含边数最多的匹配
4. 增广路径：匹配边和非匹配边交替出现的路径，且起点和终点都是未匹配顶点

匈牙利算法核心思想
算法基于一个关键定理：一个匹配是最大匹配当且仅当不存在增广路径。通过不断寻找增广路径并"翻转"路径上的匹配状态，可以逐步增大匹配。

算法步骤详解

步骤1：初始化

• 创建匹配数组match[]，记录每个V集合顶点匹配的U集合顶点（初始为-1）
• 初始化匹配大小为0

步骤2：为每个U集合顶点寻找匹配

• 遍历U集合中的每个顶点u
• 对于每个u，执行深度优先搜索寻找增广路径

步骤3：DFS寻找增广路径

function dfs(u, visited):
    遍历u的所有邻接顶点v（v属于V集合）
    如果v未被访问：
        标记v为已访问
        如果v未匹配，或者v已匹配但可以从match[v]找到新的增广路径：
            将u与v匹配
            返回匹配成功
    返回匹配失败

步骤4：路径翻转操作

• 当找到增广路径时，将路径上的匹配边变为非匹配边，非匹配边变为匹配边
• 这样匹配大小增加1

具体示例演示

考虑二分图：
U = {1, 2, 3}, V = {4, 5, 6}
边：1-4, 1-5, 2-5, 2-6, 3-4

迭代过程：

1. 顶点1匹配顶点4 → 匹配：{(1,4)}
2. 顶点2尝试匹配顶点5 → 成功 → 匹配：{(1,4), (2,5)}
3. 顶点3尝试匹配顶点4：
   • 顶点4已匹配顶点1
   • 尝试为顶点1重新匹配顶点5
   • 顶点5已匹配顶点2
   • 尝试为顶点2重新匹配顶点6 → 成功
   • 路径翻转后匹配：{(1,5), (2,6), (3,4)}

算法复杂度分析

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

关键优化技巧

1. 使用访问标记数组避免重复搜索
2. 在DFS前先尝试贪心匹配
3. 使用BFS层次遍历优化搜索顺序

实际应用场景

• 任务分配问题
• 婚姻稳定匹配
• 资源调度
• 网络流量分配

通过这种逐步构建匹配并不断优化的方法，匈牙利算法能够高效地找到二分图的最大匹配。