编辑代码

import java.util.*;

public class KruskalMST {

    static class Edge implements Comparable<Edge> {
        int src, dest, weight;

        public Edge(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge other) {
            return this.weight - other.weight;
        }
    }

    static class DisjointSet {
        int[] parent;
        int[] rank;

        public DisjointSet(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = 0;
            }
        }

        public int find(int u) {
            if (parent[u] != u) {
                parent[u] = find(parent[u]);
            }
            return parent[u];
        }

        public void union(int u, int v) {
            int uRoot = find(u);
            int vRoot = find(v);

            if (uRoot == vRoot) {
                return;
            }

            if (rank[uRoot] < rank[vRoot]) {
                parent[uRoot] = vRoot;
            } else if (rank[uRoot] > rank[vRoot]) {
                parent[vRoot] = uRoot;
            } else {
                parent[vRoot] = uRoot;
                rank[uRoot]++;
            }
        }
    }

    public static void kruskalMST(List<Edge> edges, int numVertices) {
        // 1. 对边按权重排序
        Collections.sort(edges);

        // 2. 创建一个并查集
        DisjointSet disjointSet = new DisjointSet(numVertices);

        // 3. 初始化最小生成树
        List<Edge> mst = new ArrayList<>();

        // 4. 遍历每条边
        for (Edge edge : edges) {
            int src = edge.src;
            int dest = edge.dest;

            // 5. 检查是否会导致环
            if (disjointSet.find(src) != disjointSet.find(dest)) {
                // 6. 不会导致环，加入最小生成树
                mst.add(edge);
                disjointSet.union(src, dest);
            }
        }

        // 7. 打印最小生成树
        System.out.println("最小生成树：");
        for (Edge edge : mst) {
            System.out.println("(" + edge.src + ", " + edge.dest + ") : " + edge.weight);
        }
    }

    public static void main(String[] args) {
        // 图的边集
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 4));
        edges.add(new Edge(0, 2, 4));
        edges.add(new Edge(1, 2, 2));
        edges.add(new Edge(1, 3, 3));
        edges.add(new Edge(2, 3, 3));
        edges.add(new Edge(2, 4, 2));
        edges.add(new Edge(3, 4, 1));

        // 图的顶点数
        int numVertices = 5;

        // 计算最小生成树
        kruskalMST(edges, numVertices);
    }
}