在二分图最大匹配问题中，匈牙利算法是入门的标准解法，但面对左右两侧节点都达到数万甚至数十万的稠密图时，它的 O(VE) 复杂度会立刻成为瓶颈。Hopcroft-Karp 算法通过每轮同时搜索多条最短增广路，将增广轮数从 O(V) 降到 O(sqrt(V))，是实际工程中更可靠的选择。要在 Python 中实现它，核心不是简单套用模板，而是理解 BFS 分层与 DFS 增广之间的关系。
二分图最大匹配的目标是在左右两个点集之间选择尽量多的边，使任意两条边都不共享端点。匈牙利算法每次只寻找一条增广路，找到后立刻翻转匹配状态，这样虽然实现简单，但在最坏情况下可能退化为 O(VE)。而 Hopcroft-Karp 算法每一次迭代会先通过 BFS 找到所有长度相同的最短增广路，再由 DFS 批量增广，从而大幅减少迭代次数。
一、从交替路到最短增广路：核心思想
在二分图中，匹配边和未匹配边交替出现的路径称为交替路。如果一条交替路的起点和终点都是未匹配节点，那么它被称为增广路。增广路的特殊之处在于，只要把路径上的匹配边和未匹配边互换，匹配数就能增加 1。匈牙利算法正是不断重复这个翻转过程，直到找不到增广路为止。
问题在于，如果每次随意选择一条很长的增广路，图结构可能在若干次操作后变得非常不利，导致后续搜索反复走回头路。Hopcroft-Karp 的核心改进是：每一轮只处理当前图中长度最短的一批增广路。因为最短增广路的长度只会随着匹配数增加而变长，而路径长度达到 O(sqrt(V)) 以后，剩余未匹配节点数量已经很少，可以在少量轮数内结束。
这个改进带来了明确的复杂度上界。假设左部点数为 n，右部点数为 m，总点数为 V，边数为 E，Hopcroft-Karp 的时间复杂度为 O(E sqrt(V))，空间复杂度为 O(V + E)。相比匈牙利算法的 O(VE)，在 E 接近 V^2 的稠密图上，提升是数量级的。
二、BFS分层与DFS增广的协作机制
Hopcroft-Karp 算法的每一轮分为两个阶段。第一阶段用 BFS 构建分层图。把所有未匹配的左部节点作为起点，距离记为 0，然后沿着未匹配边走到右部节点，再沿着匹配边回到左部节点，如此交替前进。当一个未匹配的右部节点第一次被访问时，当前距离就是本轮最短增广路的长度，BFS 可以停止继续深入。
BFS 完成后，每个节点都带有一个 dist 值，表示从起点到该节点的最短交替路径长度。第二阶段用 DFS 寻找增广路，但必须严格沿着 dist 值递增 1 的方向前进。例如，从左部节点 u 出发，只能走向满足 dist[pair_v[v]] == dist[u] + 1 的右部节点 v。这条限制保证了 DFS 找到的路径全部是当前最短长度，而且路径之间不会共享节点。
DFS 每次成功找到一条增广路，就立即翻转匹配关系，然后把该左部节点标记为已处理。如果某个节点已经无法继续扩展，就把它的 dist 值设为无穷大，避免后续重复访问。这样一轮 BFS 加多轮 DFS 可以同时增广多条互不相交的路径，而不是像匈牙利算法那样一次只处理一条。
三、Python代码实现步骤
实现时通常使用邻接表存储左部节点到右部节点的边。还需要维护三个核心数组：pair_u 记录左部节点当前匹配的右部节点，pair_v 记录右部节点当前匹配的左部节点，dist 记录 BFS 分层距离。为了统一处理未匹配状态，可以引入一个哨兵节点 NIL，其值为左部节点总数 n。
下面是完整的 Python 实现，包含 BFS 分层、DFS 增广和主循环三个部分。
from collections import deque
class HopcroftKarp:
def __init__(self, n, m, adj):
self.n = n
self.m = m
self.adj = adj
self.NIL = n
self.pair_u = [self.NIL] * n
self.pair_v = [self.NIL] * m
self.dist = [0] * (n + 1)
def bfs(self):
q = deque()
INF = float('inf')
for u in range(self.n):
if self.pair_u[u] == self.NIL:
self.dist[u] = 0
q.append(u)
else:
self.dist[u] = INF
self.dist[self.NIL] = INF
while q:
u = q.popleft()
if self.dist[u] < self.dist[self.NIL]:
for v in self.adj[u]:
if self.dist[self.pair_v[v]] == INF:
self.dist[self.pair_v[v]] = self.dist[u] + 1
if self.pair_v[v] != self.NIL:
q.append(self.pair_v[v])
return self.dist[self.NIL] != INF
def dfs(self, u):
if u != self.NIL:
for v in self.adj[u]:
if self.dist[self.pair_v[v]] == self.dist[u] + 1 and self.dfs(self.pair_v[v]):
self.pair_v[v] = u
self.pair_u[u] = v
return True
self.dist[u] = float('inf')
return False
return True
def max_matching(self):
matching = 0
while self.bfs():
for u in range(self.n):
if self.pair_u[u] == self.NIL and self.dfs(u):
matching += 1
return matching
代码中的 NIL 哨兵节点用于表示未匹配状态。当 BFS 到达未匹配右部节点 v 时，pair_v[v] 等于 NIL，因此 dist[NIL] 会被更新为最短增广路长度。随后 BFS 只会在 dist[u] 小于 dist[NIL] 的范围内继续扩展，从而把搜索范围限制在当前最短层次内。
DFS 部分的递归逻辑是：当尝试从左部节点 u 走向右部节点 v 时，如果 v 已经匹配，就继续递归检查 v 的匹配对象 pair_v[v] 是否能够重新匹配到其他右部节点。递归返回 True 表示可以腾出 v，这时就更新匹配关系。递归深度最坏可能达到节点数量级，对于超大图可以适当调高 Python 的递归限制，或改写为显式栈版本。
四、复杂度分析、优化细节与适用场景
Hopcroft-Karp 算法的时间复杂度为 O(E sqrt(V))，这个界来自对增广轮数的分析。每一轮 BFS 和 DFS 的总代价为 O(E)，而增广轮数不超过 O(sqrt(V))。对于左右部点数分别为 n 和 m 的二分图，如果 E 很小，匈牙利算法已经足够快；但当 E 接近 n*m 时，Hopcroft-Karp 的优势非常明显。
在 Python 实现中，邻接表使用 list 而不是字典可以降低常数因子。BFS 使用 collections.deque 保证入队和出队都是 O(1)，DFS 中每次失败后把 dist 置为无穷大可以避免重复扫描。递归写法简洁但可能受递归深度限制，如果图规模超过数千节点，建议显式设置 sys.setrecursionlimit，或把 DFS 改写成迭代版本。
该算法适用于无权二分图的最大基数匹配，例如任务分配、广告匹配、课程安排和推荐系统中的冷启动配对。如果边有权重，需要求解最大权匹配，则应使用 KM 算法或最小费用最大流。此外，Hopcroft-Karp 也是学习网络流和 Dinic 算法的良好前导，因为它的分层增广思想与 Dinic 的层次图非常相似。
在实际工程中，如果数据规模不大，优先选择实现简单、不易出错的匈牙利算法。当节点规模达到数万、边数接近百万级别，并且对运行时间敏感时，再切换到 Hopcroft-Karp。理解它的 BFS 分层与 DFS 批量增广机制，能够帮助开发者在面对更复杂的图匹配问题时，灵活设计出更高效的解决方案。
Hopcroft-Karp算法二分图最大匹配Python修改时间：2026-08-26 10:08:20