算法概述
Hopcroft-Karp算法是解决二分图最大匹配问题的经典算法，由John Hopcroft和Richard Karp于1973年提出。该算法在标准匈牙利算法（DFS增广路）的基础上引入了分层BFS思想，将时间复杂度从O(VE)优化到O(E√V)，在处理大规模二分图时具有显著优势。
本文将深入讲解Hopcroft-Karp算法的核心思想，并给出完整的Java实现，包含图的构建、分层BFS、DFS增广以及复杂度分析。
核心思想
二分图与匹配
二分图G=(U,V,E)的顶点集可划分为两个不相交的子集U和V，使得每条边都连接U中的一个顶点和V中的一个顶点。匹配是指一组没有公共顶点的边集合。最大匹配即包含边数最多的匹配。
增广路定理
Berge定理指出：一个匹配是最大匹配，当且仅当图中不存在增广路。增广路是指起点和终点均为未匹配顶点的交替路（匹配边与非匹配边交替出现）。沿着增广路翻转匹配状态，可使匹配大小增加1。
Hopcroft-Karp的优化策略
传统匈牙利算法每次只寻找一条增广路，时间复杂度为O(VE)。Hopcroft-Karp算法的核心改进在于：
- 分层BFS：从所有未匹配的U集合顶点同时出发，沿交替路进行BFS，构建距离层次图，找到最短的增广路集合
- 批量DFS增广：在分层图的基础上，从每个未匹配的U集合顶点出发进行DFS，只沿着BFS构建的距离层次前进，一次性找到多条不相交的最短增广路
- 交替执行：重复执行分层BFS和批量DFS增广，直到不存在增广路为止
由于每次找到的增广路都是当前最短的，且增广路长度严格递增，算法最多执行O(√V)轮即可收敛。
完整Java实现
import java.util.*;
/**
* Hopcroft-Karp算法实现二分图最大匹配
* 时间复杂度: O(E * sqrt(V))
* 空间复杂度: O(V + E)
*/
public class HopcroftKarp {
// 无穷大距离标记
private static final int INF = Integer.MAX_VALUE;
// 邻接表: U集合中每个顶点对应的V集合邻接顶点列表
private final List<Integer>[] graph;
// U集合顶点数
private final int nU;
// V集合顶点数
private final int nV;
// pairU[i] = U集合中顶点i匹配的V集合顶点编号，-1表示未匹配
private final int[] pairU;
// pairV[j] = V集合中顶点j匹配的U集合顶点编号，-1表示未匹配
private final int[] pairV;
// dist[i] = BFS分层图中U集合顶点i到起点的距离
private final int[] dist;
/**
* 构造函数
* @param nU U集合顶点数（编号0到nU-1）
* @param nV V集合顶点数（编号0到nV-1）
*/
@SuppressWarnings("unchecked")
public HopcroftKarp(int nU, int nV) {
this.nU = nU;
this.nV = nV;
this.graph = new ArrayList[nU];
for (int i = 0; i < nU; i++) {
graph[i] = new ArrayList<>();
}
this.pairU = new int[nU];
this.pairV = new int[nV];
this.dist = new int[nU];
Arrays.fill(pairU, -1);
Arrays.fill(pairV, -1);
}
/**
* 添加二分图边（从U集合指向V集合）
* @param u U集合顶点编号 [0, nU)
* @param v V集合顶点编号 [0, nV)
*/
public void addEdge(int u, int v) {
if (u < 0 || u >= nU || v < 0 || v >= nV) {
throw new IllegalArgumentException("顶点编号越界");
}
graph[u].add(v);
}
/**
* 执行Hopcroft-Karp算法，返回最大匹配数
*/
public int maxMatching() {
int matching = 0;
// 循环执行分层BFS + 批量DFS增广，直到不存在增广路
while (bfs()) {
// 从每个未匹配的U集合顶点尝试DFS增广
for (int u = 0; u < nU; u++) {
if (pairU[u] == -1) {
if (dfs(u)) {
matching++;
}
}
}
}
return matching;
}
/**
* 分层BFS：构建距离层次图，找到最短增广路的长度
* 返回true表示存在增广路
*/
private boolean bfs() {
ArrayDeque<Integer> queue = new ArrayDeque<>();
// 初始化：将所有未匹配的U集合顶点加入队列，距离设为0
// 已匹配的U集合顶点距离设为INF（尚未到达）
for (int u = 0; u < nU; u++) {
if (pairU[u] == -1) {
dist[u] = 0;
queue.add(u);
} else {
dist[u] = INF;
}
}
// 设置一个虚拟距离，表示是否到达过未匹配的V集合顶点
// 如果BFS结束时没有到达任何未匹配的V顶点，则不存在增广路
boolean foundAugmentingPath = false;
while (!queue.isEmpty()) {
int u = queue.poll();
// 遍历u的所有邻接顶点v
for (int v : graph[u]) {
// 获取v的匹配对象u2（可能为-1）
int u2 = pairV[v];
if (u2 != -1 && dist[u2] == INF) {
// v已匹配给u2，通过匹配边到达u2
// u2的距离为u的距离+2（非匹配边u->v，匹配边v->u2）
dist[u2] = dist[u] + 2;
queue.add(u2);
} else if (u2 == -1) {
// v未匹配，找到一条增广路的终点
foundAugmentingPath = true;
}
}
}
return foundAugmentingPath;
}
/**
* DFS增广：在分层图上从u出发寻找增广路
* 只沿着BFS构建的距离层次前进，保证找到的是最短增广路
*/
private boolean dfs(int u) {
for (int v : graph[u]) {
int u2 = pairV[v];
// 如果v未匹配，或者v的匹配对象u2可以通过分层图继续扩展
// 注意：这里通过dist[u2] == dist[u] + 2来确保只走最短路径
if (u2 == -1 || (dist[u2] == dist[u] + 2 && dfs(u2))) {
// 更新匹配关系
pairU[u] = v;
pairV[v] = u;
return true;
}
}
// 从u出发无法找到增广路，标记dist[u]防止重复访问
dist[u] = INF;
return false;
}
/**
* 获取匹配结果
* @return U集合中每个顶点匹配的V集合顶点，-1表示未匹配
*/
public int[] getPairU() {
return pairU.clone();
}
/**
* 打印匹配结果
*/
public void printMatching() {
System.out.println("最大匹配数: " + maxMatching());
for (int u = 0; u < nU; u++) {
if (pairU[u] != -1) {
System.out.println("U" + u + " <-> V" + pairU[u]);
}
}
}
// ==================== 测试主程序 ====================
public static void main(String[] args) {
// 示例：员工-任务分配问题
// U集合：4个员工 (0,1,2,3)
// V集合：5个任务 (0,1,2,3,4)
// 边表示员工可以执行的任务
HopcroftKarp hk = new HopcroftKarp(4, 5);
// 员工0可以执行任务0,1
hk.addEdge(0, 0);
hk.addEdge(0, 1);
// 员工1可以执行任务1,2
hk.addEdge(1, 1);
hk.addEdge(1, 2);
// 员工2可以执行任务2,3
hk.addEdge(2, 2);
hk.addEdge(2, 3);
// 员工3可以执行任务0,3,4
hk.addEdge(3, 0);
hk.addEdge(3, 3);
hk.addEdge(3, 4);
int maxMatch = hk.maxMatching();
System.out.println("最大匹配数: " + maxMatch); // 期望输出4
System.out.println("匹配详情:");
int[] matching = hk.getPairU();
for (int u = 0; u < matching.length; u++) {
if (matching[u] != -1) {
System.out.println(" 员工" + u + " -> 任务" + matching[u]);
}
}
// 性能测试：大规模随机二分图
System.out.println("\n=== 大规模性能测试 ===");
int testNU = 5000;
int testNV = 5000;
int testEdges = 20000;
HopcroftKarp largeHK = new HopcroftKarp(testNU, testNV);
Random rand = new Random(42);
for (int i = 0; i < testEdges; i++) {
largeHK.addEdge(rand.nextInt(testNU), rand.nextInt(testNV));
}
long start = System.currentTimeMillis();
int largeMatch = largeHK.maxMatching();
long end = System.currentTimeMillis();
System.out.println("顶点数: " + (testNU + testNV));
System.out.println("边数: " + testEdges);
System.out.println("最大匹配数: " + largeMatch);
System.out.println("运行时间: " + (end - start) + "ms");
}
}
算法正确性分析
Hopcroft-Karp算法的正确性依赖于以下关键性质：
性质1（最短增广路不相交）：在同一轮BFS构建的分层图中，从各个未匹配U顶点出发的DFS找到的增广路是顶点不相交的。这是因为一旦某个顶点被用于增广路，其匹配状态即被更新，后续DFS不会再经过该顶点。
性质2（增广路长度单调递增）：设第k轮找到的最短增广路长度为L_k，则L_{k+1} > L_k。这是因为第k轮已经找到了所有长度为L_k的增广路并进行了增广，剩余的增广路必然更长。
性质3（轮数上界）：由于增广路长度最多为O(V)，且每轮长度严格递增，而长度为l的增广路最多使匹配数增加O(V/l)条，因此总轮数为O(√V)。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(E√V) | 每轮BFS+DFS为O(E)，共O(√V)轮 |
| 空间复杂度 | O(V+E) | 邻接表、匹配数组、距离数组 |
| 与匈牙利算法对比 | O(VE) vs O(E√V) | 稠密图和大规模图优势显著 |
应用场景
- 任务分配：将n个工人分配给m个任务，每个工人有技能限制
- 网络流建模：二分图最大匹配可转化为最大流问题
- 资源调度：CPU核心与进程、频谱与用户的匹配问题
- 推荐系统：用户与商品的二分图匹配推荐
小结
Hopcroft-Karp算法通过分层BFS与批量DFS增广的协同策略，将二分图最大匹配的时间复杂度优化至O(E√V)。理解该算法的关键在于掌握增广路定理、最短增广路的不相交性质以及增广路长度的单调递增特性。在实际工程中，当二分图规模达到数千顶点、数万边时，Hopcroft-Karp相比朴素的匈牙利算法通常能提升数十倍性能。
