Hopcroft-Karp 算法求二分图最大匹配 题目描述 给定一个二分图 \( G = (U, V, E) \)，其中 \( U \) 和 \( V \) 是两个不相交的顶点集合，\( E \) 是连接 \( U \) 和 \( V \) 的边集。目标是找到一种匹配（即没有两条边共享一个顶点的边集），使得匹配的边数最大化。Hopcroft-Karp 算法通过多阶段广度优先搜索（BFS）和深度优先搜索（DFS）来高效求解该问题，时间复杂度为 \( O(\sqrt{|V|} \cdot |E|) \)，优于朴素匈牙利算法的 \( O(|V| \cdot |E|) \)。 解题步骤详解 1. 核心思想 分层图构建 ：通过 BFS 从所有未匹配的 \( U \) 顶点出发，构建分层图，标记顶点到起点的距离（层数）。 增广路径查找 ：通过 DFS 在分层图中寻找不相交的增广路径（即路径的边交替属于匹配和非匹配，且起点和终点均未匹配）。 多路径优化 ：每阶段尽可能多地找到不相交的增广路径，一次性更新匹配，减少 BFS 次数。 2. 算法流程 初始化 匹配数组 \( \text{match}[ v ] \)：记录 \( V \) 中顶点 \( v \) 匹配的 \( U \) 中顶点（未匹配则为空）。 距离数组 \( \text{dist}[ u ] \)：在 BFS 中记录 \( U \) 中顶点 \( u \) 到起点的距离。 阶段循环 BFS 构建分层图 ： 队列初始化：将所有未匹配的 \( U \) 顶点加入队列，距离设为 0。 遍历队列： 对当前顶点 \( u \in U \)，遍历其所有邻居 \( v \in V \)。 若 \( v \) 未匹配，则找到增广路径，返回 true。 若 \( v \) 已匹配，则将其匹配的顶点 \( u' \in U \) 加入队列，更新 \( \text{dist}[ u'] = \text{dist}[ u ] + 2 \)。 若未找到增广路径，返回 false，算法终止。 DFS 查找增广路径 ： 对每个未匹配的 \( U \) 顶点 \( u \)，调用 DFS 沿分层图（仅遍历距离递增的边）寻找增广路径。 找到路径后，反转匹配状态（匹配边变非匹配，非匹配边变匹配）。 3. 举例说明 考虑二分图： \( U = \{u1, u2, u3\}, V = \{v1, v2, v3\} \) 边集： \( u1-v1, u1-v2, u2-v2, u3-v3 \) 初始匹配 ：空 阶段 1 ： BFS 从所有 \( u1, u2, u3 \) 出发： \( u1 \) 到 \( v1, v2 \)（未匹配），找到增广路径。 同时 DFS 找到路径 \( u1-v1 \)，匹配 \( (u1,v1) \)。 阶段 2 ： BFS 从未匹配的 \( u2, u3 \) 出发： \( u2 \) 到 \( v2 \)（未匹配），找到路径 \( u2-v2 \)，匹配 \( (u2,v2) \)。 \( u3 \) 到 \( v3 \)（未匹配），匹配 \( (u3,v3) \)。 结果 ：最大匹配为 3 条边。 4. 关键优化 距离标签剪枝 ：DFS 中只访问距离递增的顶点，避免重复搜索。 多路径并行 ：每阶段找到所有可能的不相交增广路径，使匹配大小至少增加 1，阶段数最多 \( O(\sqrt{|V|}) \)。 5. 复杂度分析 BFS 和 DFS 每阶段耗时 \( O(|E|) \)。 阶段数最多 \( O(\sqrt{|V|}) \)，总复杂度 \( O(\sqrt{|V|} \cdot |E|) \)。 通过分层图与多路径增广的结合，Hopcroft-Karp 算法显著提升了二分图最大匹配的求解效率。