U = {u1, u2, u3}, V = {v1, v2, v3}
边集: (u1,v1), (u1,v2), (u2,v2), (u3,v2), (u3,v3)

Hopcroft-Karp算法求二分图最大匹配 题目描述 给定一个二分图 \( G = (V, E) \)，其中顶点集 \( V \) 被划分为两个不相交的子集 \( U \) 和 \( V \)，边集 \( E \) 仅包含连接 \( U \) 和 \( V \) 的边。目标是找到该二分图的最大匹配，即包含尽可能多边的子集 \( M \subseteq E \)，使得 \( M \) 中任意两条边不共享公共顶点。 Hopcroft-Kap算法通过多路径增广策略，在 \( O(\sqrt{|V|} \cdot |E|) \) 时间内求解该问题，优于匈牙利算法的 \( O(|V| \cdot |E|) \) 复杂度。 解题步骤 算法核心思想 通过广度优先搜索（BFS）同时寻找多条最短增广路径，避免单次增广的局限性。 利用深度优先搜索（DFS）沿BFS生成的层次图进行多路径增广，提升匹配效率。 初始化 定义匹配数组 match[] ： match[u] 表示 \( U \) 中顶点 \( u \) 的匹配顶点（属于 \( V \)），未匹配时设为 -1 ；同理定义 match[v] 用于 \( V \) 中顶点。 定义距离数组 dist[] ：记录BFS过程中各顶点到未匹配顶点的最短距离（仅对 \( U \) 中的顶点需要）。 BFS构建层次图 从所有未匹配的 \( U \) 中顶点出发，进行多源BFS： 初始化队列，将所有未匹配的 \( u \in U \) 的 dist[u] 设为0并入队。 遍历队列中的顶点： 若当前顶点 \( u \in U \)：检查其所有邻居 \( v \in V \)。若 \( v \) 未在BFS中被访问过，则更新 dist[v] = dist[u] + 1 ，并将 match[v] （即 \( v \) 的匹配顶点）入队。 若当前顶点 \( v \in V \)：仅当其已匹配时，将 match[v] 入队并更新距离。 若BFS遇到未匹配的 \( V \) 中顶点，说明存在增广路径，返回 true ；否则返回 false 。 DFS进行多路径增广 对每个未匹配的 \( u \in U \)，调用DFS尝试增广： 遍历 \( u \) 的所有邻居 \( v \)： 若 dist[v] == dist[u] + 1 （满足层次约束），递归检查 match[v] ： 若 match[v] 未匹配或从 match[v] 出发可找到增广路径，则更新匹配关系（将 \( u \) 与 \( v \) 匹配），并返回 true 。 若所有邻居均无法增广，返回 false 。 算法流程 循环执行以下步骤直至无法增广： 调用BFS构建层次图。若无可达未匹配顶点，终止循环。 对每个未匹配的 \( u \in U \)，调用DFS尝试增广。每次成功增广使匹配数加1。 示例说明 考虑二分图： 初始匹配 ： match[] 初始为 -1 。 第一次BFS ：从未匹配的 u1, u2, u3 出发，构建层次图（例如 u1 → v1, v2 等）。 第一次DFS ：从 u1 找到增广路径 u1-v1 ，匹配数=1； u2 找到 u2-v2 ，匹配数=2； u3 找到 u3-v3 ，匹配数=3。 最终得到最大匹配大小为3。 关键点 BFS确保每次增广路径最短，避免长路径导致的低效。 DFS同时增广多条路径，减少迭代次数。 复杂度优化源于每次迭代增广多条路径，将DFS的搜索深度控制在 \( O(\sqrt{|V|}) \) 内。