Hopcroft–Karp 算法

分层交替图 ​

给二分图公理库二分图Bipartite graph顶点可分成两部分且每条边跨越两部分的图。 $G=(L\cup R,E)$ 和当前匹配 $M$。BFS 从所有未匹配的 $L$ 顶点同时出发：从 $L$ 沿非匹配边到 $R$，再沿唯一匹配边回 $L$，直到首次到达未匹配的 $R$；由此得到最短增广路长度和层次。

DFS 只沿层数严格增加的允许边寻找增广路。找到一条后立即翻转其边，并阻止同阶段复用顶点；不必枚举全部最短路，只需得到一个 maximal vertex-disjoint family。

正确性与阶段界 ​

同阶段所有路径等长且顶点不交，可同时增广。DFS 阻塞当前层次图后，不再存在该长度的增广路，所以下一阶段最短增广路严格变长。若最短长度不超过 $\sqrt{V}$，最多有 $\sqrt{V}$ 个长度阶段；若已超过 $\sqrt{V}$，由匹配对称差分解，当前匹配距最大匹配少于 $\sqrt{V}$ 条增广路。故阶段数 $O(\sqrt{V})$，每阶段 BFS+DFS 为 $O(E)$。

同时增广例子 ​

招聘图中两名未匹配候选人分别通过不同岗位形成长度 1 的增广路。普通逐路算法可能每次重做搜索；Hopcroft–Karp 在同一层次图中找出两条不共享候选或岗位的路径，一阶段把匹配大小加二。

边界与实现风险 ​

一般图含奇环时交替结构需 blossom 收缩，本算法不适用。DFS 若走非分层边，下一阶段长度增长证明失效；失败顶点可标记为无穷避免同阶段反复搜索。复杂度中的 $V$ 是总顶点数、$E$ 是边数，不能写成 $n^{5/2}$ 后丢失稀疏图优势。

哨兵距离与翻转 ​

实现常设虚拟 NIL 表示所有未匹配右端。BFS 只扩展距离小于 dist[NIL] 的左顶点，确保 DFS 找的都是本阶段最短路。DFS 从每个 free 左顶点出发；递归成功时沿返回路径把 pairU、pairV 同时改写。

同阶段路径须顶点不交而非仅边不交，否则两个增广会争用同一匹配端点，翻转后不再是匹配。最大族只需 maximal：阻塞所有最短路即可推动下一阶段长度。

一个 phase 的状态变化 ​

设未匹配左点为 $u_1,u_2$，BFS 同时令二者距离为 0。若最短增广路长度为 3，DFS 只能走“非匹配边、匹配边、非匹配边”的层次边；找到经 $u_1$ 的路径并翻转后，相关顶点在本 phase 内封锁，DFS 再为 $u_2$ 找一条顶点不交路径。

实现通常设置哨兵 NIL 表示未匹配端点：

1. BFS 只建立到最短 NIL 距离为止的层次；
2. DFS 遇到非层次边立即跳过；
3. 某左点搜索失败后把其距离设为无穷，避免本 phase 重搜；
4. 成功路径回溯时同时更新左右两侧的 mate 数组。

一个 maximal 最短路族被全部增广后，下一条增广路严格更长。长度较短时，顶点不交性限制 phase 数；长度已大时，任一增广路消耗许多顶点，剩余匹配差也小。两段计数合起来给 $O(\sqrt{|V|})$ phases，每 phase $O(|E|)$，总计 $O(|E|\sqrt{|V|})$。

参考资料

• John Hopcroft, Richard Karp, An n^{5/2} Algorithm for Maximum Matchings in Bipartite Graphs, SIAM J. Comput., 1973.
• Cormen et al., Introduction to Algorithms, bipartite matching.