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按无权距离分层访问可达顶点的图遍历算法。，只在交替方向上前进，并在首次到达未匹配右点的距离处截断。得到的层次图精确包含当前最短增广路可能使用的方向边。随后从各未匹配左点做受层次约束的DFS公理库深度优先搜索Depth-first search · DFS沿未访问边尽可能深入后回溯的图遍历算法。，找出一个极大的、两两顶点不交的最短增广路族；每找到一条路就沿路翻转匹配状态，并封锁该路顶点供本 phase 复用。

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

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

$$|M^{\ast }|-|M|\le \frac{|V|}{\ell +1}<\sqrt{|V|}.$$

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

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

$$O(|E|\sqrt{|V|});$$

若输入必须保留孤立顶点，完整界可写成 $O(|V|+|E|\sqrt{|V|})$。空间为 $O(|V|+|E|)$。该界按显式简单二分图计数；保留重复边时，$|E|$ 应计入全部输入记录。

直觉

逐条增广会反复穿过相同的浅层交替区域。Hopcroft–Karp 先冻结“当前最短要走几步”，再一次找尽一组互不争用顶点的最短修正路线。一个 phase 结束后，所有同长度机会都已被阻断，搜索被迫转向更长的结构。

批量化能奏效，是因为匹配约束发生在顶点：两条增广路只要共享一个端点，同时翻转就可能让该点关联两条匹配边。要求顶点不交正好让各条路径的局部修改可交换。

例子与边界

令

$$L=\{a,b,c,d\},R=\{1,2,3,4\},$$

当前匹配为 $M=\{c1,d2\}$，另有边 $a1,c3,b2,d4$。未匹配左点是 $a,b$，未匹配右点是 $3,4$。BFS 找到两条长度为 $3$ 的最短增广路

$$a-1-c-3,b-2-d-4.$$

它们顶点不交，可在同一 phase 翻转，得到 $\{a1,c3,b2,d4\}$，匹配大小从 $2$ 增至 $4$。若两条候选路共享右点 $1$，只能接受其中一条；仅仅边不交并不足够。

实现常用虚拟 NIL 表示未匹配右端。BFS 只扩展距离小于 dist[NIL] 的左点；DFS 只走能使层次增加的交替边，失败后把该左点距离设为无穷，避免本 phase 重搜。成功回溯时必须同时更新左右两侧 mate 数组，否则两份匹配表示会不一致。

一般非二分图中的奇交替圈会让这套左右定向失效，最大匹配需要 blossom 收缩等方法。平行边对顶点匹配没有额外作用，可以预先合并；若不合并，只会增加扫描成本。孤立顶点合法且永远未匹配，不应造成 BFS 反复入队。

推论与应用

把二分图匹配归约为单位容量流时，左点只有一条来自源的入弧，右点只有一条通往汇的出弧，得到Dinic 算法公理库Dinic 算法Dinic's algorithm分层残量网络上反复计算阻塞流的最大流算法。的 unit network。Hopcroft–Karp 直接在交替图上实现同一“BFS 分层 + 阻塞最短增广路”机制，无需显式存储超级源、超级汇及其弧。

算法输出最大基数匹配，不处理边权、偏好稳定性或顶点多重容量。加权指派需要费用/势函数方法，医院—住院医稳定匹配又优化另一种偏好条件；共享二分图输入不意味着目标相同。

最大匹配还可结合 Kőnig 定理构造同大小的最小顶点覆盖：从未匹配左点沿最终交替可达关系取集合 $Z$，覆盖可取 $(L\setminus Z)\cup (R\cap Z)$。这一对同值证书可用于独立核验匹配大小。

参考资料

• John E. Hopcroft and Richard M. Karp, “An $n^{5/2}$ Algorithm for Maximum Matchings in Bipartite Graphs,” SIAM Journal on Computing 2(4), 1973, pp. 225–231。
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Ch. 25。
• Bernhard Korte and Jens Vygen, Combinatorial Optimization: Theory and Algorithms, 6th ed., Springer, 2018, bipartite matching and augmenting paths。