xxx 最大二分匹配的 Hopcroft-Karp 算法

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

解题过程

1. 基本概念

• 匹配：边集合 M ⊆ E，其中任意两条边不共享顶点
• 最大匹配：包含边数最多的匹配
• 交替路径：路径上的边交替属于匹配 M 和不属于匹配 M
• 增广路径：起点和终点都是未匹配顶点的交替路径

2. 算法核心思想
Hopcroft-Karp 算法通过多轮 BFS 同时寻找多条最短增广路径，显著提高效率：

• 时间复杂度 O(√|V| × |E|)，比匈牙利算法的 O(|V|×|E|) 更优
• 核心思想：在每轮迭代中同时寻找所有长度相同的最短增广路径

3. 算法步骤详解

步骤1：初始化

# 定义数据结构
match_X = {}  # X 集合中顶点的匹配对象
match_Y = {}  # Y 集合中顶点的匹配对象  
dist = {}     # BFS 中的距离标记

# 初始化所有顶点为未匹配状态
for x in X:
    match_X[x] = None
for y in Y: 
    match_Y[y] = None

步骤2：BFS 分层
从所有未匹配的 X 顶点开始进行 BFS，构建分层图：

def BFS():
    queue = deque()
    
    # 初始化距离
    for x in X:
        if match_X[x] is None:  # 未匹配的 X 顶点
            dist[x] = 0
            queue.append(x)
        else:
            dist[x] = float('inf')
    
    dist[None] = float('inf')  # 特殊标记
    
    while queue:
        x = queue.popleft()
        if dist[x] < dist[None]:
            for y in graph[x]:  # x 的所有邻居
                # 如果 y 已匹配，检查其匹配对象
                if match_Y[y] is not None:
                    next_x = match_Y[y]
                    if dist[next_x] == float('inf'):
                        dist[next_x] = dist[x] + 1
                        queue.append(next_x)
                else:
                    # 找到未匹配的 Y 顶点，路径结束
                    dist[None] = dist[x] + 1
    
    return dist[None] != float('inf')  # 是否存在增广路径

步骤3：DFS 寻找增广路径
在分层图上进行 DFS，寻找顶点不相交的增广路径：

def DFS(x):
    if x is None:
        return True
    
    for y in graph[x]:
        # 检查是否在分层图中且距离递增
        if match_Y[y] is not None:
            next_x = match_Y[y]
            if dist[next_x] == dist[x] + 1 and DFS(next_x):
                # 找到增广路径，更新匹配
                match_X[x] = y
                match_Y[y] = x
                return True
        else:
            # 直接连接到未匹配的 Y 顶点
            if dist[None] == dist[x] + 1:
                match_X[x] = y
                match_Y[y] = x
                return True
    
    dist[x] = float('inf')  # 标记为已访问
    return False

步骤4：主算法

def hopcroft_karp():
    matching = 0
    
    while BFS():  # 存在增广路径
        for x in X:
            if match_X[x] is None:  # 未匹配的 X 顶点
                if DFS(x):
                    matching += 1
    
    return matching

4. 执行过程示例
考虑二分图：

• X = {1, 2, 3}, Y = {4, 5, 6}
• 边：1-4, 1-5, 2-5, 3-5, 3-6

第1轮迭代：

• BFS 找到距离为1的增广路径
• DFS 可能找到路径 1-4，匹配：{1-4}
• 匹配数：1

第2轮迭代：

• BFS 找到距离为3的增广路径
• DFS 可能找到路径 2-5-1-4-?（失败），然后找到路径 3-6
• 匹配：{1-4, 3-6}，匹配数：2

第3轮迭代：

• BFS 找到距离为5的增广路径
• DFS 找到路径 2-5-1-4-?（重新调整），最终得到最大匹配
• 最终匹配：{1-5, 2-4, 3-6} 或类似，匹配数：3

5. 算法分析

• 正确性：基于 Berge 引理 - 匹配是最大的当且仅当不存在增广路径
• 效率：每轮 BFS 找到所有最短增广路径，最多需要 O(√|V|) 轮
• 应用：任务分配、资源调度、网络流等场景

该算法通过分层 BFS 和并行 DFS 的高效组合，在二分图匹配问题中达到了接近线性的性能表现。