最小生成树：Kruskal算法java代码

最小生成树（Minimum Spanning Tree, MST）是指在一个加权无向图中找到一棵连接所有顶点的树，其总权重尽可能小。Kruskal算法是一种著名的用于寻找MST的贪心算法，它的基本思想是从边集合中按权重从小到大选择边，每一步都确保加入的新边不会形成环。

以下是Kruskal算法的一个简单的Java实现：

import java.util.*;

class KruskalMST {
    private int V; // 图的顶点数
    private List<Edge> edges;

    // 边类，包含边的两个端点和权重
    class Edge implements Comparable<Edge> {
        int src, dest;
        int weight;

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

        @Override
        public int compareTo(Edge e) {
            return Integer.compare(this.weight, e.weight);
        }
    }

    public KruskalMST(int v) {
        V = v;
        edges = new ArrayList<>();
    }

    // 添加边并保持边集有序
    void addEdge(int src, int dest, int weight) {
        edges.add(new Edge(src, dest, weight));
    }

    // 找到并删除当前集合中权重最小的边
    Edge findMin() {
        Collections.sort(edges);
        return edges.remove(0);
    }

    // 构建最小生成树
    List<Edge> buildMST() {
        UnionFind uf = new UnionFind(V);
        List<Edge> mst = new ArrayList<>();

        for (int i = 0; i < edges.size(); ) {
            Edge e = findMin();
            if (!uf.isSameSet(e.src, e.dest)) { // 如果它们不在同一个连通分量
                uf.union(e.src, e.dest); // 合并连通分量
                mst.add(e);
                i++;
            } else {
                i++; // 避免添加环中的边
            }
        }

        return mst;
    }
}

// 并查集辅助类
class UnionFind {
    private int[] parent;

    public UnionFind(int n) {
        parent = 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 isSameSet(int x, int y) {
        return find(x) == find(y);
    }

    // 合并集合
    void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY;
        }
    }
}