匈牙利算法(Kuhn)

What · 是什么

匈牙利算法（Kuhn 算法）求二分图最大匹配（maximum bipartite matching）：从空匹配出发，反复寻找增广路并沿其翻转匹配，直到不存在增广路——由 Berge 引理，此时匹配最大。Kuhn 版本对每个左部未匹配点做一次 DFS 找增广路，单次 O(E)，总 O(VE)。实现极简：维护右部点的匹配对象 match[v]，DFS 尝试为左部点 u 找未匹配右部点，被占用的右部点则递归让它的左部匹配对象『挪窝』。是竞赛最常用的二分图匹配模板，也是网络流与 Hopcroft-Karp 的思想基石。

Why · 为什么

How · 实现

伪代码

match[v] = -1 for v in 右部

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

matching = 0
for u in 左部:
  visited = [False] * m
  if try_kuhn(u, visited): matching += 1

Python 实现

def hungarian_maximum_matching(left_n, right_m, adj):
    """Kuhn 算法求二分图最大匹配。
    left_n/right_m: 左右部点数; adj[u]: 左部点 u 可连的右部点列表。
    返回 (最大匹配数, match: 右部点 v 匹配的左部点, -1 表示未匹配)。"""
    match = [-1] * right_m

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

    res = 0
    for u in range(left_n):
        if try_kuhn(u, [False] * right_m):
            res += 1
    return res, match


if __name__ == '__main__':
    # 手工例子: 左 {0,1,2}, 右 {0,1,2}
    adj = [[0, 1], [1], [2]]
    res, match = hungarian_maximum_matching(3, 3, adj)
    assert res == 3, res
    # 随机图与 Hopcroft-Karp/暴力交叉验证
    import random
    random.seed(5)

    def brute_max(n, m, adj):
        from itertools import combinations
        edges = []
        for u in range(n):
            for v in adj[u]:
                edges.append((u, v))
        best = 0
        for r in range(min(n, m) + 1):
            for comb in combinations(edges, r):
                lu = set(e[0] for e in comb)
                rv = set(e[1] for e in comb)
                if len(lu) == r and len(rv) == r:
                    best = max(best, r)
        return best

    for _ in range(60):
        n = random.randint(1, 5)
        m = random.randint(1, 5)
        adj = [[] for _ in range(n)]
        for u in range(n):
            for v in range(m):
                if random.random() < 0.4:
                    adj[u].append(v)
        res, _ = hungarian_maximum_matching(n, m, adj)
        assert res == brute_max(n, m, adj), (n, m, adj, res)
    print('hungarian: All tests passed.')

易错点

• visited 数组忘重置会导致同一右部点被重复递归 → 错误/死循环
• match 数组方向写反（match[左] vs match[右]）导致增广失败
• 递归让座 try_kuhn(match[v], visited) 忘记传 visited，导致循环依赖
• 左部点遍历到匹配点仍要尝试（可能换座得到更大的匹配），不能跳过已匹配左部点
• 二分图前提：非二分图直接跑会得到错误结果（需先 bipartite-check）
• 稠密大图 O(VE) 超时：n≥1e4 或 E 大时应换 Hopcroft-Karp

例题

信源

• 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
• CP-Algorithms✓ https://cp-algorithms.com/graph/kuhn_maximum_bipartite_matching.html
• 书籍✓ CPH ch20 pp191-204