引言
图的最大匹配问题是图论中的核心课题。对于二分图，匈牙利算法可以在多项式时间内求解最大匹配。但当图不是二分图时（即图中存在奇环），问题变得复杂得多——增广路径可能会形成”花”（blossom）结构。1965 年，Jack Edmonds 提出的带花树算法（Blossom Algorithm / Edmonds’ Algorithm）成功解决了这一问题，成为第一个能在多项式时间内求解一般图最大匹配的经典算法。本文将用 Java 完整实现带花树算法，并深入解析其核心思想。
问题背景
什么是匹配
图 G=(V, E) 的一个匹配是指一组没有公共顶点的边集。最大匹配就是包含边数最多的匹配。
二分图 vs 一般图
- 二分图：顶点可分为两个集合，边只在集合之间。最大匹配可用匈牙利算法 O(VE) 或 Hopcroft-Karp 算法 O(E√V) 求解
- 一般图：允许存在奇环。匈牙利算法直接失效，因为增广路径可能在奇环上”绕圈”
花的概念
在寻找增广路径时，若遇到奇环（长度为奇数的环），这个奇环就被称为花（blossom）。花有一个关键性质：环上恰有一条边不属于当前匹配，且存在一个未匹配的顶点作为花的”基”。
算法核心思想
带花树算法的核心思路是：在 BFS 搜索增广路径时，如果遇到花，就将整个花收缩为一个超级顶点，继续在收缩后的图上搜索。找到增广路径后，再逐步将花展开，恢复原始匹配。
三个关键步骤
- BFS 搜索增广路径：从所有未匹配点出发，构建交替树（alternating tree）
- 花的检测与收缩：当遇到奇环时，将花收缩为单个顶点
- 增广与展开：找到增广路径后增广匹配，并将收缩的花展开恢复
收缩花的关键观察
将花收缩为一个顶点后：
– 原图存在增广路径 ⟺ 收缩后的图存在增广路径
– 花的基点是花在交替树中距离根最近的点
– 花中除基点外的每个点，都可以通过花内的交替路径到达
Java 完整实现
import java.util.*;
/**
* 带花树算法（Blossom Algorithm / Edmonds' Algorithm）
* 求解一般图（非二分图）的最大匹配
*/
public class BlossomAlgorithm {
private int n; // 顶点数量
private List<Integer>[] adj; // 邻接表
private int[] match; // match[v] 表示 v 的匹配对象，-1表示未匹配
private int[] parent; // BFS树中的父节点
private int[] base; // 每个顶点所在花的基点
private boolean[] used; // 是否在BFS树中
private boolean[] blossom; // 是否在花中
private int[] lcaAncestor; // 用于LCA计算
private Queue<Integer> queue; // BFS队列
public BlossomAlgorithm(int n) {
this.n = n;
this.adj = new ArrayList[n];
for (int i = 0; i < n; i++) {
adj[i] = new ArrayList<>();
}
this.match = new int[n];
this.parent = new int[n];
this.base = new int[n];
this.used = new boolean[n];
this.blossom = new boolean[n];
this.lcaAncestor = new int[n];
this.queue = new LinkedList<>();
Arrays.fill(match, -1);
}
/**
* 添加无向边
*/
public void addEdge(int u, int v) {
adj[u].add(v);
adj[v].add(u);
}
/**
* 查找顶点当前所在花的基点
*/
private int findBase(int v) {
if (base[v] != v) {
base[v] = findBase(base[v]);
}
return base[v];
}
/**
* 计算两个顶点在BFS树中的LCA（最近公共祖先）
*/
private int lca(int a, int b) {
boolean[] visited = new boolean[n];
// 从 a 向上标记祖先
while (true) {
a = findBase(a);
visited[a] = true;
if (match[a] == -1) break; // 到达根
a = parent[match[a]];
}
// 从 b 向上找第一个被标记的祖先
while (true) {
b = findBase(b);
if (visited[b]) return b;
b = parent[match[b]];
}
}
/**
* 标记花上的所有顶点
* @param v 花的起始顶点
* @param anc LCA（花的基点）
* @param u 与v配对的另一端点
*/
private void markBlossom(int v, int anc, int u) {
while (findBase(v) != anc) {
blossom[findBase(v)] = true;
blossom[findBase(match[v])] = true;
parent[v] = u;
u = match[v];
v = parent[match[v]];
}
}
/**
* 收缩花：将花上的所有顶点的基点设为anc
*/
private void contractBlossom(int anc, int u, int v) {
Arrays.fill(blossom, false);
markBlossom(u, anc, v);
markBlossom(v, anc, u);
// 将花中所有顶点的基点统一为anc
for (int i = 0; i < n; i++) {
if (blossom[findBase(i)]) {
base[i] = anc;
if (!used[i]) {
used[i] = true;
queue.offer(i);
}
}
}
}
/**
* 通过增广路径增广匹配
* @param v 增广路径的终点
*/
private void augmentPath(int v) {
while (v != -1) {
int pv = parent[v];
int nxt = match[pv];
match[v] = pv;
match[pv] = v;
v = nxt;
}
}
/**
* 从根节点 root 开始BFS搜索增广路径
* @param root 起始的根节点（未匹配点）
* @return 是否找到增广路径
*/
private boolean bfs(int root) {
Arrays.fill(used, false);
Arrays.fill(parent, -1);
for (int i = 0; i < n; i++) {
base[i] = i;
}
used[root] = true;
queue.clear();
queue.offer(root);
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : adj[u]) {
if (findBase(u) == findBase(v)) continue; // 同一花中，跳过
if (match[u] == v) continue; // 已匹配边，跳过
if (v == root || (match[v] != -1 && parent[match[v]] != -1)) {
// 遇到花（奇环）
int anc = lca(u, v);
contractBlossom(anc, u, v);
contractBlossom(anc, v, u);
} else if (parent[v] == -1) {
parent[v] = u;
if (match[v] == -1) {
// 找到增广路径
augmentPath(v);
return true;
} else {
// 继续BFS
used[match[v]] = true;
queue.offer(match[v]);
}
}
}
}
return false;
}
/**
* 求解一般图的最大匹配
* @return 最大匹配的边数
*/
public int maxMatching() {
int matching = 0;
for (int i = 0; i < n; i++) {
if (match[i] == -1) {
// 从未匹配点开始BFS
if (bfs(i)) {
matching++;
}
}
}
return matching;
}
/**
* 获取匹配结果
* @return 匹配对列表
*/
public List<int[]> getMatchingPairs() {
List<int[]> pairs = new ArrayList<>();
boolean[] visited = new boolean[n];
for (int i = 0; i < n; i++) {
if (match[i] != -1 && !visited[i]) {
visited[i] = true;
visited[match[i]] = true;
pairs.add(new int[]{i, match[i]});
}
}
return pairs;
}
/**
* 获取某个顶点的匹配对象
*/
public int getMatch(int v) {
return match[v];
}
/**
* 验证匹配的正确性（每条边没有公共顶点）
*/
public boolean validateMatching() {
boolean[] covered = new boolean[n];
for (int i = 0; i < n; i++) {
if (match[i] != -1) {
if (covered[i] || covered[match[i]]) {
return false; // 顶点被多条边覆盖
}
if (match[match[i]] != i) {
return false; // 匹配不对称
}
covered[i] = true;
covered[match[i]] = true;
}
}
return true;
}
/**
* 打印匹配结果
*/
public void printMatching() {
System.out.println("Maximum matching size: " + maxMatching());
System.out.println("Matching pairs:");
List<int[]> pairs = getMatchingPairs();
for (int[] pair : pairs) {
System.out.println(" " + pair[0] + " - " + pair[1]);
}
System.out.println("Valid: " + validateMatching());
}
// ==================== 应用示例 ====================
/**
* 示例1：简单三角形（3个顶点的完全图）
*/
public static void demoTriangle() {
System.out.println("=== Demo 1: Triangle (3 vertices) ===");
BlossomAlgorithm ba = new BlossomAlgorithm(3);
ba.addEdge(0, 1);
ba.addEdge(1, 2);
ba.addEdge(2, 0);
ba.printMatching();
// 三角形中最大匹配为1条边
}
/**
* 示例2：五边形（5个顶点的环）
*/
public static void demoPentagon() {
System.out.println("\n=== Demo 2: Pentagon (5 vertices) ===");
BlossomAlgorithm ba = new BlossomAlgorithm(5);
ba.addEdge(0, 1);
ba.addEdge(1, 2);
ba.addEdge(2, 3);
ba.addEdge(3, 4);
ba.addEdge(4, 0);
ba.printMatching();
// 五边形中最大匹配为2条边
}
/**
* 示例3：包含花的复杂图
*/
public static void demoComplexGraph() {
System.out.println("\n=== Demo 3: Complex Graph with Blossom ===");
// 构建一个会触发花收缩的图
BlossomAlgorithm ba = new BlossomAlgorithm(7);
ba.addEdge(0, 1);
ba.addEdge(1, 2);
ba.addEdge(2, 3);
ba.addEdge(3, 0); // 形成四边形 0-1-2-3-0
ba.addEdge(1, 4);
ba.addEdge(4, 5);
ba.addEdge(5, 6);
ba.printMatching();
}
/**
* 示例4：完全图 K4
*/
public static void demoCompleteGraphK4() {
System.out.println("\n=== Demo 4: Complete Graph K4 ===");
BlossomAlgorithm ba = new BlossomAlgorithm(4);
for (int i = 0; i < 4; i++) {
for (int j = i + 1; j < 4; j++) {
ba.addEdge(i, j);
}
}
ba.printMatching();
// K4中最大匹配为2条边
}
public static void main(String[] args) {
demoTriangle();
demoPentagon();
demoComplexGraph();
demoCompleteGraphK4();
}
}
算法复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 单次 BFS 增广 | O(VE) | 收缩和展开花的过程 |
| 整体最大匹配 | O(V²E) | 最多 V/2 次增广 |
| 空间复杂度 | O(V + E) | 存储图和辅助数组 |
更精细的分析表明，通过优化 LCA 计算和花收缩，时间复杂度可降至 O(V³)。Micali-Vazirani 算法进一步优化到 O(E√V)，但实现更为复杂。
算法正确性直观理解
带花树算法的正确性建立在以下关键观察上：
- 花收缩保持增广路径存在性：若原图有增广路径，收缩花后的图也有；反之亦然
- 花的基点性质：花中恰有一条边不在匹配中，且基点可通过花内交替路径到达任何其他点
- BFS 树的交替性质：从根到任何顶点的路径都是交替路径（匹配边与非匹配边交替）
应用场景
带花树算法广泛应用于：
- 一般图最大匹配：求解任意图的最大匹配
- 中国邮路问题：求解邮递员最短路线
- 任务分配：非二分图场景下的任务配对
- 化学结构分析：分子图中的匹配问题
- 博弈论：某些博弈中的状态分析
总结
带花树算法通过巧妙地收缩和展开花结构，将一般图的最大匹配问题转化为可在多项式时间内求解的问题。理解花的检测、收缩与展开机制，是掌握这一算法的关键。尽管其时间复杂度不如二分图匹配算法高效，但带花树算法仍是求解一般图最大匹配最经典和教学价值最高的方法。
