Boruvka算法详解（Java语言实现最小生成树的高效方法）

Boruvka算法 vs 其他MST算法

• Kruskal算法：按边权排序，逐条加入不形成环的边。
• Prim算法：从一个点出发，每次加入连接已选点集与未选点集中权重最小的边。
• Boruvka算法：每轮所有连通分量同时向外扩展，天然适合并行计算。

Boruvka算法的时间复杂度为 O(E log V)，其中 E 是边数，V 是顶点数。虽然在串行实现中不如Kruskal或Prim常用，但其并行特性使其在分布式系统中具有优势。

Java实现Boruvka算法

下面我们用Java一步步实现Boruvka算法。我们将使用并查集（Union-Find）数据结构来高效管理连通分量。

步骤概览：

1. 初始化并查集，每个顶点自成一个连通分量。
2. 重复以下过程，直到只剩一个连通分量：
• 对每个连通分量，找到连接它与其他分量的最小权重边。
• 将这些最小边加入MST，并合并对应的连通分量。

完整Java代码实现：

import java.util.*;class Edge {    int src, dest, weight;        public Edge(int src, int dest, int weight) {        this.src = src;        this.dest = dest;        this.weight = weight;    }}class Graph {    int V, E;    Edge[] edges;        public Graph(int V, int E) {        this.V = V;        this.E = E;        edges = new Edge[E];    }}// 并查集类class Subset {    int parent;    int rank;}public class BoruvkaMST {        // 查找根节点（带路径压缩）    static int find(Subset subsets[], int i) {        if (subsets[i].parent != i)            subsets[i].parent = find(subsets, subsets[i].parent);        return subsets[i].parent;    }        // 合并两个集合（按秩合并）    static void union(Subset subsets[], int x, int y) {        int xroot = find(subsets, x);        int yroot = find(subsets, y);                if (subsets[xroot].rank < subsets[yroot].rank)            subsets[xroot].parent = yroot;        else if (subsets[xroot].rank > subsets[yroot].rank)            subsets[yroot].parent = xroot;        else {            subsets[yroot].parent = xroot;            subsets[xroot].rank++;        }    }        // Boruvka算法主函数    static void boruvkaMST(Graph graph) {        int V = graph.V, E = graph.E;        Edge[] edges = graph.edges;                // 初始化并查集        Subset[] subsets = new Subset[V];        for (int v = 0; v < V; ++v) {            subsets[v] = new Subset();            subsets[v].parent = v;            subsets[v].rank = 0;        }                // 记录每个连通分量的最小边        Edge[] cheapest = new Edge[V];                int numTrees = V; // 当前连通分量数量        int mstWeight = 0; // MST总权重                // 当连通分量数量大于1时继续        while (numTrees > 1) {            // 初始化 cheapest 数组            Arrays.fill(cheapest, null);                        // 遍历所有边，更新每个连通分量的最小出边            for (int i = 0; i < E; i++) {                int set1 = find(subsets, edges[i].src);                int set2 = find(subsets, edges[i].dest);                                // 如果边连接两个不同分量                if (set1 != set2) {                    // 更新 set1 的 cheapest 边                    if (cheapest[set1] == null ||                        edges[i].weight < cheapest[set1].weight)                        cheapest[set1] = edges[i];                                        // 更新 set2 的 cheapest 边                    if (cheapest[set2] == null ||                        edges[i].weight < cheapest[set2].weight)                        cheapest[set2] = edges[i];                }            }                        // 将 cheapest 边加入 MST            for (int i = 0; i < V; i++) {                if (cheapest[i] != null) {                    int set1 = find(subsets, cheapest[i].src);                    int set2 = find(subsets, cheapest[i].dest);                                        if (set1 != set2) {                        System.out.println("边 " + cheapest[i].src + " - " +                                         cheapest[i].dest + " 权重 " +                                         cheapest[i].weight + " 加入MST");                        mstWeight += cheapest[i].weight;                        union(subsets, set1, set2);                        numTrees--;                    }                }            }        }                System.out.println("最小生成树总权重: " + mstWeight);    }        // 测试示例    public static void main(String[] args) {        /* 创建如下图：           0        1           |\      /|         4 | \2  3/ | 2           |  \  /  |           |   \/   |           2----3              1        */        int V = 4; // 顶点数        int E = 5; // 边数        Graph graph = new Graph(V, E);                // 添加边        graph.edges[0] = new Edge(0, 1, 10);        graph.edges[1] = new Edge(0, 2, 6);        graph.edges[2] = new Edge(0, 3, 5);        graph.edges[3] = new Edge(1, 3, 15);        graph.edges[4] = new Edge(2, 3, 4);                boruvkaMST(graph);    }}

代码说明

上述代码实现了完整的Boruvka算法。关键点包括：

• Subset 类用于并查集，支持路径压缩和按秩合并，提升效率。
• cheapest 数组记录每个连通分量当前的最小出边。
• 主循环中，每轮遍历所有边，更新每个分量的 cheapest 边，然后统一合并。

总结

通过本教程，你已经掌握了如何用Java语言实现Boruvka算法来求解最小生成树。虽然该算法在实际应用中不如Kruskal或Prim常见，但它展示了图论中一种独特的“并行”思维模式，也是理解高级图算法的重要基础。

无论你是学习图论算法的新手，还是希望拓展算法知识的开发者，Boruvka算法都值得你深入理解。动手运行上面的代码，修改图的结构，观察输出结果，你会对MST有更直观的认识！