二分图最大匹配的 Hopcroft-Karp 算法

题目描述

给定一个二分图 \(G = (U, V, E)\)，其中 \(U\) 和 \(V\) 是两部分互不相交的顶点集合，\(E\) 是连接 \(U\) 和 \(V\) 的边集合。求该二分图的一个最大匹配，即一个边集 \(M \subseteq E\)，使得 \(M\) 中任意两条边没有公共顶点，且 \(M\) 的边数尽可能大。

Hopcroft-Kop 算法是一种高效的算法，能在 \(O(\sqrt{|V|} \cdot |E|)\) 的时间复杂度内找到最大匹配，特别适用于稠密或大规模的二分图。

解题过程

1. 基本概念

• 匹配：边集 \(M\)，其中任意两条边不共享顶点。
• 最大匹配：边数最多的匹配。
• 交错路径：一条路径，其边交替属于匹配 \(M\) 和非匹配边 \(E \setminus M\)。
• 增广路径：起点和终点都是未匹配顶点的交错路径。增广路径的长度一定是奇数。
• 增广：将增广路径上的边在匹配与非匹配之间互换，可以使匹配大小增加 1。

2. 算法核心思想

Hopcroft-Kop 算法通过分层 BFS 同时寻找多条不相交的增广路径，并用 DFS 沿着这些路径进行增广，从而在每轮迭代中增加多条匹配边，极大减少了增广次数。

关键观察：

• 每次 BFS 构建从所有未匹配的 \(U\) 顶点出发的层次图。
• DFS 在层次图上寻找并增广多条不相交的增广路径。
• 算法在 \(O(\sqrt{n})\) 轮内结束，每轮复杂度 \(O(m)\)，总复杂度 \(O(\sqrt{n} \cdot m)\)。

3. 数据结构准备

• adj[u]：存储 \(U\) 中顶点 \(u\) 的邻居列表（在 \(V\) 中）。
• pairU[u]：\(U\) 中顶点 \(u\) 在匹配中对应的 \(V\) 中顶点，若未匹配则为 -1。
• pairV[v]：\(V\) 中顶点 \(v\) 在匹配中对应的 \(U\) 中顶点，若未匹配则为 -1。
• dist[u]：BFS 中从 \(u\) 到起点的距离（用于分层和剪枝）。
• NIL：一个特殊值，表示 BFS 中的“超级源点”。

4. 算法步骤详解

步骤 1：初始化

• 将 pairU 和 pairV 全部初始化为 -1（表示未匹配）。
• 匹配大小 matching = 0。

步骤 2：BFS 构建层次图

• 目标：为所有未匹配的 \(U\) 顶点计算到“虚拟汇点”的最短距离（即最短增广路径长度）。
• 过程：
  1. 初始化队列，将所有未匹配的 \(U\) 顶点入队，dist[u] = 0。
  2. 对于已匹配的 \(U\) 顶点，dist[u] = INF。
  3. 从这些顶点开始 BFS，每次从 \(u\) 访问其邻居 \(v\)（通过非匹配边），再从 \(v\) 访问其匹配的 \(u'\)（通过匹配边），直到遇到未匹配的 \(V\) 顶点。
  4. 记录每个顶点的 dist 值，构建层次结构。

步骤 3：DFS 寻找增广路径

• 对每个未匹配的 \(U\) 顶点，尝试用 DFS 在层次图上找到一条到未匹配 \(V\) 顶点的路径。
• DFS 沿着 dist 递减的方向进行（dist[v] == dist[u] + 1），确保沿着最短增广路径前进。
• 找到一条增广路径后，立即增广（交换匹配状态），并标记路径上的顶点为“已使用”，避免冲突。

步骤 4：迭代

• 重复步骤 2 和 3，直到 BFS 找不到任何增广路径（即没有未匹配的 \(V\) 顶点可达），此时匹配达到最大。

5. 时间复杂度分析

• 每轮 BFS + DFS 的复杂度为 \(O(|E|)\)。
• 总轮数为 \(O(\sqrt{|V|})\)，因为每轮至少增加 \(\sqrt{|V|}\) 条匹配边（由数学证明可得）。
• 总复杂度：\(O(\sqrt{|V|} \cdot |E|)\)。

6. 举例说明

考虑二分图：

• \(U = \{1, 2, 3\}\)
• \(V = \{a, b, c\}\)
• 边：1-a, 1-b, 2-a, 2-c, 3-b

初始：所有顶点未匹配。

第 1 轮 BFS：

• 未匹配 U：{1,2,3}，dist 均为 0，入队。
• 从 1 访问 a（非匹配边），a 未匹配 ⇒ 发现增广路径 1-a。
• 从 2 访问 a，但 a 已被访问，跳过。
• 从 3 访问 b（非匹配边），b 未匹配 ⇒ 发现增广路径 3-b。

第 1 轮 DFS 增广：

• 增广 1-a：匹配 1-a。
• 增广 3-b：匹配 3-b。

第 2 轮 BFS：

• 未匹配 U：{2}，dist[2]=0。
• 从 2 访问 a（非匹配边），a 已匹配 1，从 a 访问 1（匹配边），dist[1]=1。
• 从 1 访问 b（非匹配边），b 已匹配 3，从 b 访问 3（匹配边），dist[3]=2。
• 从 3 访问 c（非匹配边），c 未匹配 ⇒ 发现增广路径 2-a-1-b-3-c。

第 2 轮 DFS 增广：

• 沿路径 2-a-1-b-3-c 增广：
  • 原匹配：1-a, 3-b。
  • 新匹配：2-a, 1-b, 3-c。

匹配完成：

• 最大匹配为 3 条边：2-a, 1-b, 3-c。

7. 核心代码框架（C++风格伪代码）

vector<int> adj[MAX_U];
int pairU[MAX_U], pairV[MAX_V], dist[MAX_U];
int U, V; // 左右部顶点数

bool bfs() {
    queue<int> q;
    for (int u = 1; u <= U; u++) {
        if (pairU[u] == -1) {
            dist[u] = 0;
            q.push(u);
        } else {
            dist[u] = INF;
        }
    }
    bool found = false;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            int u2 = pairV[v];
            if (u2 != -1 && dist[u2] == INF) {
                dist[u2] = dist[u] + 1;
                q.push(u2);
            } else if (u2 == -1) {
                found = true; // 找到未匹配的V顶点
            }
        }
    }
    return found;
}

bool dfs(int u) {
    for (int v : adj[u]) {
        int u2 = pairV[v];
        if (u2 == -1 || (dist[u2] == dist[u] + 1 && dfs(u2))) {
            pairU[u] = v;
            pairV[v] = u;
            return true;
        }
    }
    dist[u] = INF;
    return false;
}

int hopcroft_karp() {
    fill(pairU, pairU + U + 1, -1);
    fill(pairV, pairV + V + 1, -1);
    int matching = 0;
    while (bfs()) {
        for (int u = 1; u <= U; u++) {
            if (pairU[u] == -1 && dfs(u)) {
                matching++;
            }
        }
    }
    return matching;
}

总结

Hopcroft-Kop 算法通过分层 BFS+多路增广 DFS，将寻找增广路径的过程批量处理，显著提升了二分图最大匹配的求解效率。它在实践中对大规模图非常有效，是二分图匹配问题的首选算法之一。