随机收缩算法入门（用Java轻松掌握图论中的经典启发式方法）

随机收缩算法的基本思想

该算法的核心操作是：随机选择一条边，然后将这条边连接的两个顶点“收缩”成一个新顶点。重复此过程，直到图中只剩下两个顶点。此时，连接这两个顶点的边的数量就是当前的一次割值。

由于每次选择边是随机的，单次运行可能得不到真正的最小割。但通过多次重复运行，我们可以以高概率获得正确答案。

Java实现步骤详解

我们将使用邻接表来表示图，并借助 Java 的 ArrayList 和 HashMap 来高效管理顶点和边。

1. 定义图的数据结构

import java.util.*;public class Graph {    private Map<Integer, List<Integer>> adjList;    public Graph() {        this.adjList = new HashMap<>();    }    public void addEdge(int u, int v) {        adjList.computeIfAbsent(u, k -> new ArrayList<>()).add(v);        adjList.computeIfAbsent(v, k -> new ArrayList<>()).add(u);    }    public Set<Integer> getVertices() {        return adjList.keySet();    }    public List<Integer> getNeighbors(int vertex) {        return new ArrayList<>(adjList.getOrDefault(vertex, new ArrayList<>()));    }    // 合并顶点 u 和 v，将 v 合并到 u    public void contract(int u, int v) {        // 将 v 的所有邻居添加到 u        for (int neighbor : getNeighbors(v)) {            if (neighbor != u) {                adjList.get(u).add(neighbor);                adjList.get(neighbor).add(u);            }            // 从 neighbor 的邻居列表中移除 v            adjList.get(neighbor).remove(Integer.valueOf(v));        }        // 移除顶点 v        adjList.remove(v);        // 清理 u 自身的自环（u 到 u 的边）        adjList.put(u, adjList.get(u).stream().filter(x -> x != u).collect(ArrayList::new, ArrayList::add, ArrayList::addAll));    }}

2. 实现随机收缩算法

import java.util.*;public class KargerMinCut {    public static int findMinCut(Graph graph) {        Random rand = new Random();        Graph copy = deepCopy(graph); // 需要深拷贝，避免修改原图        while (copy.getVertices().size() > 2) {            // 随机选择一条边            List<Integer> vertices = new ArrayList<>(copy.getVertices());            int u = vertices.get(rand.nextInt(vertices.size()));            List<Integer> neighbors = copy.getNeighbors(u);            if (neighbors.isEmpty()) continue;            int v = neighbors.get(rand.nextInt(neighbors.size()));            // 收缩 u 和 v            copy.contract(u, v);        }        // 剩下两个顶点，返回它们之间的边数        List<Integer> remaining = new ArrayList<>(copy.getVertices());        return copy.getNeighbors(remaining.get(0)).size();    }    // 简化版深拷贝（实际项目中建议使用更健壮的方式）    private static Graph deepCopy(Graph original) {        Graph copy = new Graph();        for (int u : original.getVertices()) {            for (int v : original.getNeighbors(u)) {                if (u < v) { // 避免重复添加无向边                    copy.addEdge(u, v);                }            }        }        return copy;    }}

3. 多次运行提高成功率

单次运行的成功概率较低（约为 $2/n^2$，其中 n 是顶点数）。为了提高准确性，我们通常运行 $n^2 \log n$ 次。

public static int kargerRepeated(Graph graph) {    int n = graph.getVertices().size();    int minCut = Integer.MAX_VALUE;    int iterations = (int) (n * n * Math.log(n));    for (int i = 0; i < iterations; i++) {        int cut = findMinCut(graph);        if (cut < minCut) {            minCut = cut;        }    }    return minCut;}

为什么这个算法有效？

随机收缩算法的关键在于：如果我们在每一步都不“破坏”真正的最小割（即不收缩最小割中的边），那么最终剩下的两个超级顶点之间的边就正好是最小割。虽然单次成功的概率不高，但通过重复运行，我们可以以极高概率逼近最优解。

总结

通过本教程，你已经掌握了如何用Java实现随机收缩算法。这种启发式算法不仅展示了概率方法在图论中的强大作用，也为解决复杂优化问题提供了新思路。无论你是学习Java优化算法的新手，还是想深入理解随机收缩算法实现的开发者，希望这篇教程都能为你带来启发。

提示：在实际应用中，可考虑使用更高效的图表示（如并查集）来优化性能。