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

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

解题过程

1. 基本概念理解

• 匹配：边的集合，其中任意两条边没有公共顶点
• 最大匹配：包含边数最多的匹配
• 增广路径：从一个未匹配点出发，交替经过匹配边和非匹配边，最终到达另一个未匹配点的路径

2. 算法核心思想
匈牙利算法基于以下原理：一个匹配是最大匹配当且仅当图中不存在增广路径。算法通过不断寻找增广路径并"翻转"路径上的边（匹配边变非匹配边，非匹配边变匹配边）来增加匹配的大小。

3. 算法步骤详解

步骤1：初始化

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

步骤2：为每个X顶点寻找匹配

for 每个x∈X:
    重置visited数组为false
    如果能为x找到匹配，则匹配数加1

步骤3：DFS寻找增广路径

function dfs(x):
    for 每个与x相邻的y∈Y:
        if y未被访问:
            标记y为已访问
            if y未匹配 或 与y匹配的x'可以找到新匹配:
                将y匹配给x
                返回true
    返回false

4. 具体执行过程

以二分图为例：
X = {A, B, C}, Y = {D, E, F}
边：A-D, A-E, B-D, B-F, C-E, C-F

迭代1：为A寻找匹配

• 从A开始DFS，尝试匹配D（未匹配），成功匹配A-D

迭代2：为B寻找匹配

• 从B开始，尝试匹配D（已匹配A）
• 检查A是否可以换匹配：A尝试匹配E（未匹配），成功
• 更新匹配：B-D, A-E

迭代3：为C寻找匹配

• 从C开始，尝试匹配E（已匹配A）
• 检查A是否可以换匹配：A尝试匹配D（已匹配B）
• 检查B是否可以换匹配：B尝试匹配F（未匹配），成功
• 更新匹配：C-E, A-D, B-F

5. 算法复杂度分析

• 时间复杂度：O(|X|×|E|)
• 空间复杂度：O(|X|+|Y|+|E|)

6. 关键点说明

• 增广路径的长度总是奇数
• 每次找到增广路径，匹配数增加1
• 算法保证在有限步内找到最大匹配
• 对于稠密图，可以使用BFS优化寻找增广路径的过程