Hopcroft-Karp 算法

Hopcroft-Karp 算法是一种计算二分图最大匹配的算法,由美国计算机科学家约翰·霍普克罗夫特(John Hopcroft)与理查德·卡普(Richard Karp)于 1973 年提出,两人均为图灵奖得主。该算法的时间复杂度为 O(E√V),其中 E 为边数、V 为顶点数,长期以来是二分图匹配的标准高效解法。

概述

二分图最大匹配问题要求在两侧顶点之间选出尽可能多的边,使任何顶点至多出现在一条选中边上,典型场景如任务分配、稳定配对前的可行性判断等。经典匈牙利算法每次沿一条增广路扩大匹配,总复杂度 O(VE);Hopcroft-Karp 的关键改进是每一阶段同时找出一批顶点不相交的最短增广路一起增广,阶段数被证明只有 O(√V) 级别。

核心原理

算法按阶段迭代,每个阶段包含两步:

• BFS 分层:从所有未匹配的左侧顶点出发,交替沿非匹配边与匹配边做广度优先搜索,构建分层图,确定当前最短增广路长度。
• DFS 增广:在分层图上做深度优先搜索,贪心地找出一个极大的顶点不相交最短增广路集合,并同时翻转这些路径上的匹配状态。

可以证明,每个阶段后最短增广路长度严格增加,而当最短增广路长度超过 √V 时,剩余可增广次数不超过 √V,因此总阶段数为 O(√V),每阶段代价 O(E),得到总复杂度 O(E√V)。

应用场景

该算法广泛用于任务与资源分配、竞赛图论题、稀疏矩阵置换(把最大匹配用于矩阵对角化预处理)、以及作为求二分图最小点覆盖与最大独立集的基础(借助柯尼希定理)。在单位容量网络中,它也可以看作 Dinic 最大流算法的特例。

常见问题

问:它与匈牙利算法有什么区别？答:两者都基于增广路,匈牙利算法一次增广一条路,复杂度 O(VE);Hopcroft-Karp 每阶段批量增广多条最短路,复杂度降为 O(E√V),在大规模稀疏图上优势明显。

问:它能处理带权匹配吗？答:不能,带权二分图最大权匹配需要 KM 算法或最小费用流,Hopcroft-Karp 只解决不带权的最大基数匹配。

问:与 Dinic 算法是什么关系？答:把二分图匹配建成源汇单位容量网络后,Dinic 算法的行为与 Hopcroft-Karp 基本一致,复杂度分析也相同,可以视为同一思想在不同框架下的表述。