每日算法 — 使用java实现Karger算法：随机收缩与全局最小割

问题背景

全局最小割（Global Minimum Cut）问题要求：给定一个无向带权图 G=(V, E)，找到将图分成两个非空连通分量的边集，使得这些边的权重之和最小。

与 s-t 最小割问题不同，全局最小割不指定源点和汇点，需要在所有可能的划分中寻找最优解。该问题在网络可靠性分析、图像分割、社区发现等领域有广泛应用。

Karger 算法核心思想

David Karger 于 1993 年提出的随机算法通过边收缩（Edge Contraction）优雅地解决了这个问题：

1. 边收缩操作：随机选择一条边 (u, v)，将顶点 u 和 v 合并为一个新顶点，同时移除所有 u 和 v 之间的边（自环）
2. 重复收缩：不断执行随机边收缩，直到图中只剩下两个超顶点
3. 输出割集：这两个超顶点之间的边即为全局最小割的一个候选解

为什么随机收缩有效

关键观察：设最小割的边数为 k。对于具有 n 个顶点的图，每个顶点的度数至少为 k（否则该顶点本身就是一个更小的割）。因此图中总边数至少为 nk/2。

随机选择一条边属于最小割的概率为：k/|E| 小于等于 k/(nk/2) = 2/n

这意味着在收缩初期（n 较大时），选中危险边（最小割边）的概率很低。随着顶点数减少，概率逐渐增大，但此时大多数非最小割边已被收缩。

Java 实现

并查集辅助的边收缩实现

import java.util.*;

public class KargerAlgorithm {
    static class Edge {
        int u, v, weight;
        Edge(int u, int v, int weight) {
            this.u = u;
            this.v = v;
            this.weight = weight;
        }
    }

    static class UnionFind {
        int[] parent, rank;
        UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        int find(int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        }
        boolean union(int x, int y) {
            int rx = find(x), ry = find(y);
            if (rx == ry) return false;
            if (rank[rx] < rank[ry]) { int t = rx; rx = ry; ry = t; }
            parent[ry] = rx;
            if (rank[rx] == rank[ry]) rank[rx]++;
            return true;
        }
    }

    /**
     * Karger 单次随机收缩算法
     * @param n 顶点数（顶点编号 0 到 n-1）
     * @param edges 边列表
     * @return 最小割候选值
     */
    public static int kargerMinCut(int n, List<Edge> edges) {
        Random rand = new Random();
        UnionFind uf = new UnionFind(n);
        int vertices = n;
        List<Edge> remaining = new ArrayList<>(edges);

        while (vertices > 2) {
            // 随机选择一条边
            int idx = rand.nextInt(remaining.size());
            Edge e = remaining.get(idx);
            int ru = uf.find(e.u);
            int rv = uf.find(e.v);

            // 如果两端已在同一连通分量，移除该边并重新选择
            if (ru == rv) {
                remaining.remove(idx);
                continue;
            }

            // 收缩这条边
            uf.union(ru, rv);
            vertices--;
            remaining.remove(idx);
        }

        // 统计两个超顶点之间的边权和
        int cutWeight = 0;
        for (Edge e : remaining) {
            int ru = uf.find(e.u);
            int rv = uf.find(e.v);
            if (ru != rv) {
                cutWeight += e.weight;
            }
        }
        return cutWeight;
    }

    /**
     * 多次运行取最优解，提升成功概率
     */
    public static int kargerRepeated(int n, List<Edge> edges, int iterations) {
        int bestCut = Integer.MAX_VALUE;
        for (int i = 0; i < iterations; i++) {
            int cut = kargerMinCut(n, new ArrayList<>(edges));
            if (cut < bestCut) bestCut = cut;
        }
        return bestCut;
    }

    public static void main(String[] args) {
        // 测试图：一个经典的最小割示例
        int n = 4;
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 1));
        edges.add(new Edge(0, 2, 1));
        edges.add(new Edge(1, 2, 1));
        edges.add(new Edge(1, 3, 1));
        edges.add(new Edge(2, 3, 1));

        int iterations = n * n * (int)Math.log(n);
        int minCut = kargerRepeated(n, edges, iterations);
        System.out.println("全局最小割: " + minCut); // 期望输出 2
    }
}

Karger-Stein 加速优化

public class KargerStein {
    static class Edge {
        int u, v;
        Edge(int u, int v) { this.u = u; this.v = v; }
    }

    static class Graph {
        int n;
        List<Edge> edges;
        Graph(int n, List<Edge> edges) {
            this.n = n;
            this.edges = new ArrayList<>(edges);
        }
    }

    /**
     * 边收缩直到剩余 t 个顶点
     */
    static Graph contract(Graph g, int t) {
        Random rand = new Random();
        UnionFind uf = new UnionFind(g.n);
        List<Edge> remaining = new ArrayList<>(g.edges);
        int vertices = g.n;

        while (vertices > t && !remaining.isEmpty()) {
            int idx = rand.nextInt(remaining.size());
            Edge e = remaining.get(idx);
            int ru = uf.find(e.u);
            int rv = uf.find(e.v);
            if (ru != rv) {
                uf.union(ru, rv);
                vertices--;
            }
            remaining.remove(idx);
        }
        return new Graph(g.n, remaining);
    }

    /**
     * Karger-Stein 递归算法
     * 关键洞察：当顶点数减少到 n/sqrt(2) 时，算法成功概率显著降低
     * 此时应分叉为两个独立的子问题
     */
    static int fastMinCut(Graph g) {
        if (g.n <= 6) {
            // 小规模用暴力法
            return bruteForceMinCut(g);
        }
        int t = (int) Math.ceil(1 + g.n / Math.sqrt(2));

        Graph g1 = contract(g, t);
        Graph g2 = contract(g, t);

        return Math.min(fastMinCut(g1), fastMinCut(g2));
    }

    static int bruteForceMinCut(Graph g) {
        // 对于小图，枚举所有 2^(n-1) 种划分
        int n = g.n;
        int minCut = Integer.MAX_VALUE;
        for (int mask = 1; mask < (1 << (n - 1)); mask++) {
            int cut = 0;
            for (Edge e : g.edges) {
                boolean inA = ((mask >> e.u) & 1) == 1;
                boolean inB = ((mask >> e.v) & 1) == 1;
                if (inA != inB) cut++;
            }
            minCut = Math.min(minCut, cut);
        }
        return minCut;
    }

    // UnionFind 定义同上
    static class UnionFind {
        int[] parent;
        UnionFind(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        int find(int x) {
            return parent[x] == x ? x : (parent[x] = find(parent[x]));
        }
        void union(int x, int y) {
            parent[find(x)] = find(y);
        }
    }
}

性能测试

public class KargerBenchmark {
    public static void main(String[] args) {
        // 生成随机稠密图
        int n = 20;
        List<KargerAlgorithm.Edge> edges = new ArrayList<>();
        Random rand = new Random(42);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (rand.nextDouble() < 0.5) {
                    edges.add(new KargerAlgorithm.Edge(i, j, rand.nextInt(10) + 1));
                }
            }
        }

        long start = System.currentTimeMillis();
        int iterations = n * n;
        int minCut = KargerAlgorithm.kargerRepeated(n, edges, iterations);
        long time = System.currentTimeMillis() - start;

        System.out.println("顶点数: " + n + ", 边数: " + edges.size());
        System.out.println("Karger 最小割: " + minCut);
        System.out.println("运行次数: " + iterations);
        System.out.println("耗时: " + time + "ms");
    }
}

算法分析

应用场景

1. 网络可靠性：评估网络在最坏情况下需要切断多少条边才能分裂
2. 图像分割：基于图割的图像前景/背景分离
3. 社区发现：社交网络中识别紧密连接的社区边界
4. 聚类分析：作为谱聚类的预处理步骤

总结

Karger 算法以惊人的简洁性解决了全局最小割这一困难问题。其核心洞察——随机收缩不会过早破坏最小割——展现了随机算法在图论中的强大威力。Karger-Stein 进一步优化，通过递归分治将复杂度从多项式级提升到近线性级。理解这一算法有助于深入掌握随机化技术的分析方法和图收缩技巧。