Hopcroft-Karp算法

What · 是什么

Hopcroft-Karp（HK）算法是二分图最大匹配的最优算法之一，复杂度 O(E√V)。它把 Kuhn 的单次单增广路升级为『每一轮找到多条互不相交的最短增广路（阻塞流）同时增广』：先 BFS 从所有未匹配左部点建层次图（dist），只到找到第一个含未匹配右部点的层为止；再按层次严格递增的限制做 DFS 找若干条点不相交的最短增广路一起翻转。最短增广路长度每轮严格增加，总轮数 O(√V)，故总复杂度 O(E√V)。实际上它是 Dinic 求二分图匹配（容量 1 网络）的特例。

Why · 为什么

How · 实现

伪代码

pairU[u] = -1 (左部 u 匹配的右部); pairV[v] = -1

bfs():
  q = 所有未匹配左部点, dist=0
  dist[NIL] = -1; found = False
  while q:
    u = pop(q)
    for v in adj[u]:
      w = pairV[v]
      if w == -1: found = True          # 找到未匹配右部点
      elif dist[w] == -1:
        dist[w] = dist[u] + 1; push(q, w)
  return found

dfs(u):
  for v in adj[u]:
    w = pairV[v]
    if w == -1 or (dist[w] == dist[u]+1 and dfs(w)):
      pairU[u] = v; pairV[v] = u; return True
  dist[u] = -1; return False

matching = 0
while bfs():
  for u in 左部点:
    if pairU[u] == -1 and dfs(u): matching += 1

Python 实现

from collections import deque


def hopcroft_karp(left_n, right_m, adj):
    """Hopcroft-Karp 求二分图最大匹配，O(E√V)。
    adj[u]: 左部点 u 的右部点邻居列表。返回 (匹配数, pairU, pairV)。"""
    pairU = [-1] * left_n
    pairV = [-1] * right_m
    NIL = left_n
    dist = [-1] * (left_n + 1)

    def bfs():
        q = deque()
        found = False
        for u in range(left_n):
            if pairU[u] == -1:
                dist[u] = 0
                q.append(u)
            else:
                dist[u] = -1
        dist[NIL] = -1
        while q:
            u = q.popleft()
            for v in adj[u]:
                w = pairV[v]
                if w == -1:
                    found = True
                elif dist[w] == -1:
                    dist[w] = dist[u] + 1
                    q.append(w)
        return found

    def dfs(u):
        for v in adj[u]:
            w = pairV[v]
            if w == -1 or (dist[w] == dist[u] + 1 and dfs(w)):
                pairU[u] = v
                pairV[v] = u
                return True
        dist[u] = -1
        return False

    res = 0
    while bfs():
        for u in range(left_n):
            if pairU[u] == -1 and dfs(u):
                res += 1
    return res, pairU, pairV


if __name__ == '__main__':
    import random

    def kuhn(n, m, adj):
        match = [-1] * m

        def tr(u, vis):
            for v in adj[u]:
                if vis[v]:
                    continue
                vis[v] = True
                if match[v] == -1 or tr(match[v], vis):
                    match[v] = u
                    return True
            return False

        r = 0
        for u in range(n):
            if tr(u, [False] * m):
                r += 1
        return r

    random.seed(5)
    for _ in range(200):
        n = random.randint(1, 20)
        m = random.randint(1, 20)
        adj = [[] for _ in range(n)]
        for u in range(n):
            for v in range(m):
                if random.random() < 0.25:
                    adj[u].append(v)
        r1, _, _ = hopcroft_karp(n, m, adj)
        r2 = kuhn(n, m, adj)
        assert r1 == r2, (n, m, adj, r1, r2)
    print('hopcroft-karp: All tests passed.')

易错点

• BFS 中未匹配右部点只是置 found=True，不能再沿它的 pairV（-1）入队
• DFS 必须先判 pairV[v]==-1 或（dist[w]==dist[u]+1 且 dfs(w)），条件顺序错误会走非层次边
• 每轮 while bfs() 后要重新对未匹配左部点 dfs，不能用缓存的上轮 dist
• dist 数组大小 left_n+1（含 NIL 哨兵），索引越界是常见 bug
• 找最大匹配数要在找到后就累加，不能在 while 结束后再数 pairU
• 图巨大时 Python 递归 dfs 每次新建 list 会慢，尽量复用数组

例题

信源

• OI Wiki✓ https://oi-wiki.org/graph/graph-matching/bigraph-match/
• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/graph/graph-matching/bigraph-match.md
• 书籍✓ Hopcroft & Karp 1973, An n^{5/2} algorithm for maximum matchings in bipartite graphs
• 书籍✓ CLRS ch26.3 (bipartite matching via max flow)