Hopcroft-Karp算法求二分图最大匹配

题目描述
给定一个二分图G=(U,V,E)，其中U和V是两个不相交的顶点集合，E是连接U和V的边集合。求该二分图的最大匹配，即找到尽可能多的边，使得这些边没有公共顶点。

算法思路
Hopcroft-Karp算法通过BFS构建层次图，然后使用DFS寻找增广路径。关键思想是每次寻找一束最短的增广路径，而不是单条路径。

详细步骤

1. 初始化

• 定义距离数组dist，记录U集合顶点到虚拟起点的距离
• 定义匹配数组pairU和pairV，记录顶点匹配关系
• 初始化所有顶点为未匹配状态

2. BFS构建层次图

• 从所有未匹配的U顶点开始BFS
• 计算每个U顶点到起点的最短距离
• 遇到未匹配的V顶点时停止当前分支
• 返回是否存在增广路径

3. DFS寻找增广路径

• 从U集合的未匹配顶点开始DFS
• 按照BFS建立的层次图前进
• 找到增广路径后更新匹配关系
• 使用递归实现路径查找

4. 算法主循环

while BFS找到增广路径:
    for u in U的未匹配顶点:
        if DFS(u)找到增广路径:
            匹配数加1

复杂度分析

• 时间复杂度：O(√|V| * |E|)
• 空间复杂度：O(|V| + |E|)

算法优势

• 相比匈牙利算法的O(|V||E|)复杂度更优
• 特别适合稠密二分图
• 实际运行效率很高

这个算法通过分层搜索和批量增广的策略，显著提高了二分图匹配的求解效率。