算法简介
一般图最大匹配问题是指：在给定的无向图中，找到一个边集使得任意两条边不共享顶点，且边集的大小最大。与二分图匹配不同，一般图中可能存在奇数长度的环（奇环），这使得匈牙利算法等二分图算法无法直接应用。Edmonds于1965年提出的Blossom算法（花收缩算法）通过在搜索过程中动态收缩奇环为单个顶点，优雅地解决了这一难题，是图论中最重要的算法之一。
核心思想
Blossom算法的核心是交错树（Alternating Tree）和花（Blossom）收缩：
- 交错树：以某个未匹配顶点为根，树边交替为非匹配边和匹配边
- 花的定义：在交错树中发现的一条连接两个同奇偶性顶点的边，与树上路径形成一个奇环
- 花收缩：将发现的奇环（花）收缩为单个超顶点，继续在收缩后的图上搜索增广路
- 展开恢复：找到增广路后，将收缩的花逐层展开，恢复出原图上的增广路
关键性质：花收缩不改变图中最大匹配的大小，因此可以在收缩后的图上安全地继续搜索。
Java实现
import java.util.*;
/**
* Edmonds Blossom算法实现
* 求解一般无向图的最大匹配
*
* @author AlgorithmDaily
*/
public class BlossomAlgorithm {
private int n; // 顶点数
private List<Integer>[] graph; // 邻接表
private int[] match; // 匹配数组，match[v]表示v的配对顶点，-1表示未匹配
private int[] parent; // BFS中的父节点
private int[] base; // 每个顶点在收缩图中的代表顶点
private boolean[] used; // 是否在交错树中
private boolean[] blossom; // 是否在花中
private int[] queue; // BFS队列
private int qh, qt; // 队列头尾指针
private int lcaIteration; // LCA计算迭代标记
private int[] lcaMark; // LCA标记数组
@SuppressWarnings("unchecked")
public BlossomAlgorithm(int n) {
this.n = n;
this.graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[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.queue = new int[n];
this.lcaMark = new int[n];
Arrays.fill(match, -1);
}
/**
* 添加无向边
*/
public void addEdge(int u, int v) {
graph[u].add(v);
graph[v].add(u);
}
/**
* 计算两个顶点在交错树中的最近公共祖先（LCA）
*/
private int lca(int a, int b) {
lcaIteration++;
while (true) {
a = base[a];
lcaMark[a] = lcaIteration;
if (match[a] == -1) break;
a = parent[match[a]];
}
while (true) {
b = base[b];
if (lcaMark[b] == lcaIteration) return b;
b = parent[match[b]];
}
}
/**
* 从花中的顶点v开始，向上标记整个花
*/
private void markPath(int v, int b, int children) {
while (base[v] != b) {
blossom[base[v]] = blossom[base[match[v]]] = true;
parent[v] = children;
children = match[v];
v = parent[match[v]];
}
}
/**
* 找到连接root和v的边，收缩形成的花
* @return 花的根（LCA）
*/
private int findBlossomRoot(int root, int v) {
int b = lca(root, v);
Arrays.fill(blossom, false);
markPath(root, b, v);
markPath(v, b, root);
return b;
}
/**
* 收缩花：将花中的所有顶点的base设为b
*/
private void contractBlossom(int b) {
for (int i = 0; i < n; i++) {
if (blossom[base[i]]) {
base[i] = b;
if (!used[i]) {
used[i] = true;
queue[qt++] = i;
}
}
}
}
/**
* 从起始顶点start开始搜索增广路
* @return 如果找到增广路返回true
*/
private boolean findAugmentingPath(int start) {
Arrays.fill(used, false);
Arrays.fill(parent, -1);
for (int i = 0; i < n; i++) {
base[i] = i;
}
used[start] = true;
qh = 0; qt = 0;
queue[qt++] = start;
while (qh < qt) {
int v = queue[qh++];
for (int to : graph[v]) {
if (base[v] == base[to] || match[v] == to) continue;
// 找到未匹配顶点，增广路 discovered
if (to == start || (match[to] != -1 && parent[match[to]] != -1)) {
int blossomRoot = findBlossomRoot(v, to);
contractBlossom(blossomRoot);
}
// to 是未访问顶点
else if (parent[to] == -1) {
parent[to] = v;
if (match[to] == -1) {
// 找到增广路，进行增广
augment(to);
return true;
}
// 继续扩展交错树
to = match[to];
used[to] = true;
queue[qt++] = to;
}
}
}
return false;
}
/**
* 沿着增广路进行增广操作
*/
private void augment(int v) {
while (v != -1) {
int pv = parent[v];
int nxt = match[pv];
match[v] = pv;
match[pv] = v;
v = nxt;
}
}
/**
* 执行Blossom算法计算最大匹配
* @return 最大匹配的边数
*/
public int maxMatching() {
int matching = 0;
// 尝试从每个未匹配顶点出发寻找增广路
for (int v = 0; v < n; v++) {
if (match[v] == -1) {
if (findAugmentingPath(v)) {
matching++;
}
}
}
return matching;
}
/**
* 获取匹配结果
* @return 匹配边的列表，每条边表示为较小的端点
*/
public List<int[]> getMatchingEdges() {
List<int[]> edges = new ArrayList<>();
boolean[] visited = new boolean[n];
for (int v = 0; v < n; v++) {
if (match[v] != -1 && !visited[v]) {
visited[v] = true;
visited[match[v]] = true;
edges.add(new int[]{Math.min(v, match[v]), Math.max(v, match[v])});
}
}
return edges;
}
/**
* 打印匹配结果
*/
public void printMatching() {
System.out.println("=== 最大匹配结果 ===");
List<int[]> edges = getMatchingEdges();
System.out.println("匹配边数: " + edges.size());
for (int[] edge : edges) {
System.out.println(" " + edge[0] + " -- " + edge[1]);
}
System.out.println("\n未匹配顶点:");
for (int v = 0; v < n; v++) {
if (match[v] == -1) {
System.out.print(" " + v);
}
}
System.out.println();
}
/**
* 主程序：演示Blossom算法
*/
public static void main(String[] args) {
// 示例1：包含三角形的图（需要花收缩）
System.out.println("=== 示例1：三角形图 ===");
BlossomAlgorithm ba1 = new BlossomAlgorithm(3);
ba1.addEdge(0, 1);
ba1.addEdge(1, 2);
ba1.addEdge(2, 0);
int match1 = ba1.maxMatching();
System.out.println("最大匹配数: " + match1 + " (期望: 1)");
ba1.printMatching();
// 示例2：五边形加对角线（经典奇环）
System.out.println("\n=== 示例2：五边形加对角线 ===");
BlossomAlgorithm ba2 = new BlossomAlgorithm(5);
// 五边形边
ba2.addEdge(0, 1);
ba2.addEdge(1, 2);
ba2.addEdge(2, 3);
ba2.addEdge(3, 4);
ba2.addEdge(4, 0);
// 对角线
ba2.addEdge(0, 2);
int match2 = ba2.maxMatching();
System.out.println("最大匹配数: " + match2 + " (期望: 2)");
ba2.printMatching();
// 示例3：复杂图（多个奇环嵌套）
System.out.println("\n=== 示例3：复杂一般图 ===");
BlossomAlgorithm ba3 = new BlossomAlgorithm(10);
// 构建一个包含多个奇环的复杂图
ba3.addEdge(0, 1); ba3.addEdge(1, 2); ba3.addEdge(2, 0); // 三角形
ba3.addEdge(2, 3); ba3.addEdge(3, 4); ba3.addEdge(4, 2); // 另一个三角形
ba3.addEdge(4, 5); ba3.addEdge(5, 6); ba3.addEdge(6, 4); // 第三个三角形
ba3.addEdge(6, 7);
ba3.addEdge(7, 8); ba3.addEdge(8, 9); ba3.addEdge(9, 7); // 第四个三角形
ba3.addEdge(0, 9); // 连接首尾
int match3 = ba3.maxMatching();
System.out.println("最大匹配数: " + match3);
ba3.printMatching();
// 示例4：Petersen图（经典一般图）
System.out.println("\n=== 示例4：Petersen图 ===");
BlossomAlgorithm petersen = new BlossomAlgorithm(10);
// 外五边形
petersen.addEdge(0, 1); petersen.addEdge(1, 2);
petersen.addEdge(2, 3); petersen.addEdge(3, 4); petersen.addEdge(4, 0);
// 内五角星
petersen.addEdge(5, 7); petersen.addEdge(7, 9);
petersen.addEdge(9, 6); petersen.addEdge(6, 8); petersen.addEdge(8, 5);
// 连接边
petersen.addEdge(0, 5); petersen.addEdge(1, 6);
petersen.addEdge(2, 7); petersen.addEdge(3, 8); petersen.addEdge(4, 9);
int petersenMatch = petersen.maxMatching();
System.out.println("Petersen图最大匹配数: " + petersenMatch + " (期望: 5)");
petersen.printMatching();
}
}
复杂度分析
- 时间复杂度：$O(V^3)$，其中 $V$ 是顶点数。每次寻找增广路需要 $O(V^2)$，最多需要 $O(V)$ 次增广。
- 空间复杂度：$O(V^2)$，使用邻接表存储图，以及多个辅助数组。
更高效的实现（如Micali-Vazirani算法）可将时间复杂度优化到 $O(V^{2.5})$ 或 $O(E \cdot \sqrt{V})$，但实现复杂度大幅提升。
算法特点与适用场景
优点：
– 能够处理任意无向图，不限于二分图
– 算法正确性有严格的数学证明
– 是求解一般图最大匹配问题的标准算法
缺点：
– 时间复杂度较高，对于稠密大图效率有限
– 实现复杂，花收缩和展开的逻辑容易出错
– 不如二分图匹配算法（匈牙利算法）高效
适用场景：一般图的最大匹配计算、Tutte矩阵与完美匹配判定、图论研究中的匹配问题、化学分子结构匹配、社交网络中的配对问题等。
