Java最小生成树实战指南（从零开始掌握Prim与Kruskal算法）

实现最小生成树的两种经典算法

在Java中，我们通常使用以下两种算法来求解最小生成树：

• Prim算法：从一个顶点出发，逐步扩展生成树，每次选择连接树与非树顶点的最小权重边。
• Kruskal算法：将所有边按权重排序，从小到大依次选择边，只要不形成环就加入生成树。

Prim算法的Java实现

Prim算法适合稠密图（边较多的情况）。下面是一个基于邻接矩阵的简单实现：

import java.util.Arrays;public class PrimMST {    private static final int INF = Integer.MAX_VALUE;    private int V; // 顶点数量    private int[][] graph; // 邻接矩阵    public PrimMST(int v) {        V = v;        graph = new int[V][V];    }    public void addEdge(int u, int v, int weight) {        graph[u][v] = weight;        graph[v][u] = weight;    }    public void primMST() {        int[] parent = new int[V];        int[] key = new int[V];        boolean[] inMST = new boolean[V];        Arrays.fill(key, INF);        key[0] = 0;        parent[0] = -1;        for (int count = 0; count < V - 1; count++) {            int u = minKey(key, inMST);            inMST[u] = true;            for (int v = 0; v < V; v++) {                if (graph[u][v] != 0 && !inMST[v] && graph[u][v] < key[v]) {                    parent[v] = u;                    key[v] = graph[u][v];                }            }        }        printMST(parent);    }    private int minKey(int[] key, boolean[] inMST) {        int min = INF, minIndex = -1;        for (int v = 0; v < V; v++) {            if (!inMST[v] && key[v] < min) {                min = key[v];                minIndex = v;            }        }        return minIndex;    }    private void printMST(int[] parent) {        System.out.println("边\t权重");        for (int i = 1; i < V; i++) {            System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);        }    }    public static void main(String[] args) {        PrimMST mst = new PrimMST(5);        mst.addEdge(0, 1, 2);        mst.addEdge(0, 3, 6);        mst.addEdge(1, 2, 3);        mst.addEdge(1, 3, 8);        mst.addEdge(1, 4, 5);        mst.addEdge(2, 4, 7);        mst.addEdge(3, 4, 9);        mst.primMST();    }}

Kruskal算法的Java实现

Kruskal算法更适合稀疏图（边较少的情况），它依赖并查集（Union-Find）数据结构来检测环。以下是完整实现：

import java.util.*;class Edge implements Comparable {    int src, dest, weight;    public int compareTo(Edge compareEdge) {        return this.weight - compareEdge.weight;    }}class Subset {    int parent, rank;}public class KruskalMST {    int V, E;    Edge[] edges;    public KruskalMST(int v, int e) {        V = v;        E = e;        edges = new Edge[E];        for (int i = 0; i < e; ++i)            edges[i] = new Edge();    }    int find(Subset subsets[], int i) {        if (subsets[i].parent != i)            subsets[i].parent = find(subsets, subsets[i].parent);        return subsets[i].parent;    }    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++;        }    }    void kruskalMST() {        Edge[] result = new Edge[V];        int e = 0;        int i = 0;        for (i = 0; i < V; ++i)            result[i] = new Edge();        Arrays.sort(edges);        Subset subsets[] = new Subset[V];        for (i = 0; i < V; ++i)            subsets[i] = new Subset();        for (int v = 0; v < V; ++v) {            subsets[v].parent = v;            subsets[v].rank = 0;        }        i = 0;        while (e < V - 1) {            Edge nextEdge = edges[i++];            int x = find(subsets, nextEdge.src);            int y = find(subsets, nextEdge.dest);            if (x != y) {                result[e++] = nextEdge;                union(subsets, x, y);            }        }        System.out.println("边\t权重");        for (i = 0; i < e; ++i)            System.out.println(result[i].src + " - " + result[i].dest + "\t" + result[i].weight);    }    public static void main(String[] args) {        int V = 4;        int E = 5;        KruskalMST graph = new KruskalMST(V, E);        graph.edges[0].src = 0; graph.edges[0].dest = 1; graph.edges[0].weight = 10;        graph.edges[1].src = 0; graph.edges[1].dest = 2; graph.edges[1].weight = 6;        graph.edges[2].src = 0; graph.edges[2].dest = 3; graph.edges[2].weight = 5;        graph.edges[3].src = 1; graph.edges[3].dest = 3; graph.edges[3].weight = 15;        graph.edges[4].src = 2; graph.edges[4].dest = 3; graph.edges[4].weight = 4;        graph.kruskalMST();    }}

总结与建议

通过本教程，你已经掌握了Java最小生成树的核心思想和两种主流算法的实现方式。如果你处理的是稠密图，推荐使用Prim算法Java实现；如果是稀疏图，则Kruskal算法Java教程中的方法更高效。这两种方法都是图论算法Java中的基础内容，建议多加练习，加深理解。

希望这篇教程能帮助你顺利入门最小生成树！如有疑问，欢迎在评论区交流讨论。