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

题目描述：
给定一个二分图G=(X∪Y, E)，其中X和Y是两个不相交的顶点集合，E是边集。我们需要找到该二分图的一个最大匹配。匹配是指边的集合M⊆E，其中任意两条边都不共享公共顶点。最大匹配是指包含边数最多的匹配。

解题过程：

1. 基本概念理解

• 二分图：顶点可划分为两个集合X和Y，所有边都连接X和Y中的顶点
• 匹配：没有公共顶点的边集合
• 增广路径：从未匹配点出发，交替经过匹配边和非匹配边，最终到达另一个未匹配点的路径

2. 算法核心思想
   匈牙利算法基于一个关键定理：一个匹配是最大匹配当且仅当图中不存在增广路径。算法通过不断寻找增广路径来扩大匹配。

3. 算法步骤详解

步骤1：初始化

• 设置所有顶点为未匹配状态
• 初始化空匹配M

步骤2：为X集合中的每个未匹配点寻找增广路径
对于X中的每个未匹配顶点u：

• 使用深度优先搜索(DFS)或广度优先搜索(BFS)从u开始寻找增广路径
• 搜索过程中需要记录路径信息

步骤3：寻找增广路径的具体过程
a) 从X中的未匹配点u开始搜索
b) 遍历u的所有邻接点v（v∈Y）
c) 如果v未匹配，则找到增广路径u-v
d) 如果v已匹配，则继续从v的匹配点开始搜索
e) 使用标记数组避免循环搜索

步骤4：路径增广
如果找到增广路径：

• 将路径上的匹配状态取反：匹配边变为非匹配边，非匹配边变为匹配边
• 这样匹配的大小增加1

步骤5：重复过程
继续为X中的其他未匹配点寻找增广路径，直到无法找到新的增广路径为止。

4. 算法实现细节

数据结构设计：

• match[y]：记录Y中顶点y匹配的X中顶点
• visited[]：标记在本次搜索中已访问的顶点

伪代码实现：

function hungarian(G):
    初始化match数组为-1（表示未匹配）
    
    for 每个x∈X:
        重置visited数组
        if dfs(x):  # 从x开始寻找增广路径
            匹配数加1
    
    return 匹配数

function dfs(x):
    for 每个与x相邻的y∈Y:
        if y未被访问:
            标记y已访问
            if y未匹配 或 dfs(match[y])为真:  # match[y]是y当前匹配的顶点
                match[y] = x
                return true
    return false

5. 时间复杂度分析

• 算法需要为X中的每个顶点执行一次DFS/BFS
• 每次搜索的时间复杂度为O(|E|)
• 总时间复杂度：O(|X|×|E|)

6. 实际应用示例
   考虑二分图：X={1,2,3}, Y={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-5，但5已匹配，为2寻找新匹配2-6，成功
• 最终匹配：1-5, 2-6, 3-4

这个算法通过系统性地寻找和增广路径，能够有效地找到二分图的最大匹配。