每日算法 — 使用java实现Blossom算法：一般图最大匹配与Edmonds花收缩策略

引言

在图论中，最大匹配问题是一个经典且重要的课题。与二分图不同，一般图（非二分图）的最大匹配问题更为复杂，因为图中可能存在奇数长度的环。Edmonds于1965年提出的Blossom算法（花算法）通过”花收缩”技术优雅地解决了这一难题，成为图论算法中的里程碑之作。

算法原理

1. 基本概念

• 匹配：图中一组没有公共顶点的边集合
• 增广路：交替路径，起点和终点都是未匹配顶点
• 花（Blossom）：以某个未匹配顶点为根的交替树中，奇数长度的环

2. 核心思想

Blossom算法的核心在于花收缩：当在搜索增广路的过程中遇到奇环（花）时，将整个花收缩为一个超级顶点，继续在收缩后的图中搜索增广路。找到增广路后，再逐步将花展开，恢复匹配。

3. 算法步骤

1. 从每个未匹配顶点出发进行BFS，构建交替树
2. 若发现增广路，直接增广
3. 若发现花，将其收缩，继续在收缩图中搜索
4. 重复直到无法找到增广路

Java实现

import java.util.*;

/**
 * Blossom算法实现一般图最大匹配
 * 时间复杂度：O(V^3)，其中V为顶点数
 */
public class BlossomAlgorithm {

    private int n;              // 顶点数量
    private int[] match;        // 匹配数组，match[v]表示v的匹配顶点
    private int[] p;            // 父节点数组，用于构建交替树
    private int[] base;         // 每个顶点所在花的基顶点
    private boolean[] used;     // 标记顶点是否在当前交替树中
    private boolean[] blossom;  // 标记顶点是否在当前花中
    private int[] q;            // BFS队列
    private int qh, qt;         // 队列头尾指针
    private List<int[]> edges;  // 边列表

    public BlossomAlgorithm(int n) {
        this.n = n;
        this.match = new int[n];
        this.p = new int[n];
        this.base = new int[n];
        this.used = new boolean[n];
        this.blossom = new boolean[n];
        this.q = new int[n];
        this.edges = new ArrayList<>();
        Arrays.fill(match, -1);
    }

    /**
     * 添加无向边
     */
    public void addEdge(int u, int v) {
        if (u != v) {
            edges.add(new int[]{u, v});
        }
    }

    /**
     * 寻找两个顶点的最近公共祖先（在交替树中）
     */
    private int lca(int a, int b) {
        boolean[] visited = new boolean[n];
        // 从a向上标记
        while (true) {
            a = base[a];
            visited[a] = true;
            if (match[a] == -1) break;
            a = p[match[a]];
        }
        // 从b向上找第一个被标记的顶点
        while (true) {
            b = base[b];
            if (visited[b]) return b;
            b = p[match[b]];
        }
    }

    /**
     * 标记花中的所有顶点
     */
    private void markBlossom(int v, int b, int a) {
        while (base[v] != b) {
            blossom[base[v]] = true;
            blossom[base[match[v]]] = true;
            p[v] = a;
            a = match[v];
            v = p[match[v]];
        }
    }

    /**
     * 收缩花
     */
    private int blossomContraction(int v, int to, int lcaVertex) {
        Arrays.fill(blossom, false);
        markBlossom(v, lcaVertex, to);
        markBlossom(to, lcaVertex, v);
        if (base[v] != lcaVertex) p[v] = to;
        if (base[to] != lcaVertex) p[to] = v;
        return lcaVertex;
    }

    /**
     * 寻找从根出发的增广路
     */
    private int findPath(int root) {
        Arrays.fill(used, false);
        Arrays.fill(p, -1);
        for (int i = 0; i < n; i++) base[i] = i;

        used[root] = true;
        qh = qt = 0;
        q[qt++] = root;

        while (qh < qt) {
            int v = q[qh++];
            for (int[] edge : edges) {
                int to = -1;
                if (edge[0] == v) to = edge[1];
                else if (edge[1] == v) to = edge[0];
                else continue;

                if (base[v] == base[to] || match[v] == to) continue;

                // 找到增广路终点（未匹配顶点）
                if (to == root || (match[to] != -1 && p[match[to]] != -1)) {
                    int curbase = lca(v, to);
                    Arrays.fill(blossom, false);
                    markBlossom(v, curbase, to);
                    markBlossom(to, curbase, v);
                    for (int i = 0; i < n; i++) {
                        if (blossom[base[i]]) {
                            base[i] = curbase;
                            if (!used[i]) {
                                used[i] = true;
                                q[qt++] = i;
                            }
                        }
                    }
                }
                // 发现未匹配顶点，找到增广路
                else if (p[to] == -1) {
                    p[to] = v;
                    if (match[to] == -1) {
                        return to; // 找到增广路终点
                    }
                    to = match[to];
                    used[to] = true;
                    q[qt++] = to;
                }
            }
        }
        return -1;
    }

    /**
     * 沿增广路增广
     */
    private void augmentPath(int v) {
        while (v != -1) {
            int pv = p[v];
            int nxt = match[pv];
            match[v] = pv;
            match[pv] = v;
            v = nxt;
        }
    }

    /**
     * 计算最大匹配
     * @return 匹配的对数
     */
    public int maxMatching() {
        int matching = 0;
        for (int v = 0; v < n; v++) {
            if (match[v] == -1) {
                int to = findPath(v);
                if (to != -1) {
                    augmentPath(to);
                    matching++;
                }
            }
        }
        return matching;
    }

    /**
     * 获取匹配结果
     */
    public List<int[]> getMatching() {
        List<int[]> result = 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;
                result.add(new int[]{i, match[i]});
            }
        }
        return result;
    }

    public static void main(String[] args) {
        // 测试案例：Petersen图，最大匹配为5
        BlossomAlgorithm ba = new BlossomAlgorithm(10);
        // Petersen图的边
        int[][] edges = {
            {0,1},{1,2},{2,3},{3,4},{4,0},      // 外五边形
            {0,5},{1,6},{2,7},{3,8},{4,9},      // 辐射边
            {5,7},{7,9},{9,6},{6,8},{8,5}       // 内五角星
        };
        for (int[] e : edges) ba.addEdge(e[0], e[1]);

        int maxMatch = ba.maxMatching();
        System.out.println("最大匹配数：" + maxMatch);
        System.out.println("匹配边：");
        for (int[] e : ba.getMatching()) {
            System.out.println("  " + e[0] + " - " + e[1]);
        }

        // 测试案例2：三角形图，最大匹配为1
        BlossomAlgorithm ba2 = new BlossomAlgorithm(3);
        ba2.addEdge(0, 1);
        ba2.addEdge(1, 2);
        ba2.addEdge(2, 0);
        System.out.println("
三角形图最大匹配：" + ba2.maxMatching());
    }
}

复杂度分析

其中V为顶点数，E为边数。虽然Edmonds原始算法的复杂度为O(V⁴)，但通过巧妙的实现优化可达到O(V³)。

应用场景

1. 人员分配问题：将任务分配给工人，考虑非二分图的兼容性约束
2. 化学结构分析：分子图匹配与结构识别
3. 计算机网络：点对点连接优化
4. 组合优化：作为其他复杂算法的子程序

总结

Blossom算法通过花收缩技术，将一般图最大匹配这一看似棘手的问题转化为可在多项式时间内求解的问题。理解花收缩的思想对于掌握高级图算法具有重要意义。