Hopcroft–Karp 算法

形式陈述 ​

给定二分图理路二分图Bipartite graph顶点可分成两个独立侧、且每条边都跨越两侧的有限简单无向图。 $G=(L\dot{\cup }R,E)$ 与当前匹配 $M$。把每条非匹配边定向为 $L\to R$，每条匹配边定向为 $R\to L$；于是从未匹配左点到未匹配右点的有向路，恰是相对于 $M$ 的增广路理路增广路Augmenting path相对于当前匹配，边在未匹配与已匹配之间交替且两个端点均未匹配的路径。。

一个 phase 先从所有未匹配的 $L$ 顶点做多源BFS理路广度优先搜索Breadth-first search · BFS按无权距离分层访问可达顶点的图遍历算法。，只在交替方向上前进，首次到达未匹配右点时记录最短距离 $\ell$，继续处理所有可能到达该层的前驱，但不再向更深层扩展。层次图保留全部最短增广路所需的方向边，也可能含最终不能到达空闲右点的分支。随后从各未匹配左点做受层次约束的DFS理路深度优先搜索Depth-first search · DFS沿未访问边尽可能深入后回溯的图遍历算法。，找出一个极大的、两两顶点不交的最短增广路族；每找到一条路就沿路翻转匹配状态，本阶段其余路径不再使用这些顶点。

每条增广路的非匹配边比匹配边多一条，翻转使 $|M|$ 增加 $1$；路径顶点不交保证同阶段的翻转彼此不冲突。DFS 达到极大后，不再有与本阶段已选路径顶点不交的旧最短增广路。新匹配的最短增广长度严格增加，理由如下。若 BFS 已找不到增广路，Berge 定理给出 $M$ 为最大匹配。

保留本阶段开始时的 BFS 层号。翻转新增的有向边都是已选层次边的反向，故沿它走会降低一层；其余旧边最多增加一层。新的空闲端点是旧空闲端点的子集，所以一条长度不超过 $\ell$ 的新增广路必须每步恰好升一层，且长度恰为 $\ell$。它不能使用任何新反向边；也不能经过已选路径的任何顶点：这些点在新匹配中都已匹配，增广路必须使用其唯一匹配边，而这些匹配边恰是本阶段新增的反向边。因此它必须与已选路径顶点不交，与极大性矛盾。

阶段数的 $O(\sqrt{|V|})$ 证明分成两段。短路阶段中，最短长度每次严格增加，因此长度不超过 $\sqrt{|V|}$ 的 phase 至多 $O(\sqrt{|V|})$ 个。设此后最短增广路至少含 $\ell >\sqrt{|V|}$ 条边，取任一最大匹配 $M^{\ast }$；对称差 $M\mathrm{△}{M}^{\ast }$ 分解出的 $|M^{\ast }|-|M|$ 条 $M$-增广路两两顶点不交，每条至少占 $\ell +1$ 个顶点，故

余下每个 phase 至少增广一条路，所以也不到 $\sqrt{|V|}$ 个。

在邻接表和单位成本 RAM 下，BFS 与带失败标记/当前邻边位置的 DFS 每 phase 共扫描 $O(|V|+|E|)$。删除孤立点后 $|E|=\mathrm{\Omega }(|V|)$，经典总界为

先花线性时间记录并剔除孤立点、只在其余图上分阶段搜索；若输出仍须保留这些未匹配顶点，完整界为 $O(|V|+|E|\sqrt{|V|})$。空间为 $O(|V|+|E|)$。该界按显式简单二分图计数；保留重复边时，$|E|$ 应计入全部输入记录。