xxx 最大二分匹配的 Hopcroft-Karp 算法 题目描述 给定一个二分图 \( G = (V, E) \)，其中顶点集 \( V \) 被划分为两个不相交的子集 \( U \) 和 \( V \)，边集 \( E \) 仅包含连接 \( U \) 和 \( V \) 的边。目标是找到该二分图的 最大匹配 ，即包含尽可能多的边的子集 \( M \subseteq E \)，使得 \( M \) 中任意两条边没有公共顶点。Hopcroft-Karp 算法通过多路径增广策略，在 \( O(\sqrt{|V|} \cdot |E|) \) 时间内高效解决该问题。 解题过程 1. 基本概念回顾 匹配 ：边的集合，其中任意两条边不共享顶点。 最大匹配 ：包含边数最多的匹配。 增广路径 ：一条交替经过匹配边和非匹配边的路径，且起点和终点均为未匹配顶点。增广路径的特性是：将其上的边状态取反（匹配边变为非匹配边，反之亦然）可使匹配大小增加 1。 2. 算法核心思想 Hopcroft-Karp 算法通过以下步骤优化匹配过程： 多路径增广 ：在单次 BFS 中同时寻找多条最短增广路径，而非一次仅增广一条路径。 分层图构建 ：使用 BFS 从所有未匹配顶点（通常固定在集合 \( U \) 中）出发，构建分层图，确保每次增广路径长度严格递增。 DFS 增广 ：在分层图上使用 DFS 寻找顶点不相交的增广路径，并一次性更新匹配。 3. 算法详细步骤 步骤 1：初始化 将匹配 \( M \) 初始化为空。 定义距离数组 \( dist \)，用于 BFS 中记录顶点到未匹配顶点的最短距离。 步骤 2：多路径增广循环 循环执行以下操作，直到无法找到增广路径： BFS 构建分层图 ： 从 \( U \) 中所有未匹配顶点出发，进行多源 BFS，仅遍历非匹配边（从 \( U \) 到 \( V \)）和匹配边（从 \( V \) 回 \( U \)）。 记录每个顶点到起点的最短距离 \( dist \)，并标记可达的顶点。 若某个未匹配顶点在 \( V \) 中被到达，则存在增广路径。 DFS 寻找顶点不相交的增广路径 ： 对 \( U \) 中每个未匹配顶点，尝试在分层图上进行 DFS（仅沿距离递减的方向移动），寻找一条到 \( V \) 中未匹配顶点的路径。 每找到一条增广路径，立即更新匹配（路径边状态取反），并确保后续 DFS 不重复使用已匹配的顶点。 更新匹配 ： 单次循环中找到的所有增广路径被同时应用，匹配大小增加路径数量。 步骤 3：终止与输出 当 BFS 无法到达 \( V \) 中任何未匹配顶点时，算法终止，当前匹配 \( M \) 即为最大匹配。 4. 关键点与复杂度分析 正确性保证 ：每次增广路径长度严格递增，确保算法在 \( O(\sqrt{|V|}) \) 次循环内终止。 时间复杂度 ： 每次 BFS/DFS 耗时 \( O(|E|) \)。 总循环次数为 \( O(\sqrt{|V|}) \)，故总复杂度为 \( O(\sqrt{|V|} \cdot |E|) \)。 优势 ：相比匈牙利算法（\( O(|V| \cdot |E|) \)），Hopcroft-Karp 在稀疏大图上效率显著提升。 5. 实例演示（简略） 考虑二分图： \( U = \{u1, u2, u3\} \), \( V = \{v1, v2, v3\} \) 边集：\( (u1,v1), (u1,v2), (u2,v2), (u3,v2), (u3,v3) \) 执行过程 ： 初始匹配为空。 第一轮 BFS 找到多条长度为 1 的增广路径（如 \( u1 \to v1 \)），通过 DFS 同时增广，匹配大小增至 2。 第二轮 BFS 找到更长路径（如 \( u3 \to v2 \to u2 \to v? \)），通过调整匹配实现最大匹配（大小为 3）。 通过分层图的约束，算法避免了冗余搜索，快速收敛到最优解。