最小生成树java实现代码kruskal

Kruskal算法是一种用于寻找无向图中最小生成树的贪心算法。以下是使用Java实现Kruskal算法的一个基本示例：

import java.util.*;

class Edge implements Comparable<Edge> {
    int u, v, w;

    public Edge(int u, int v, int w) {
        this.u = u;
        this.v = v;
        this.w = w;
    }

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

public class KruskalMST {
    private List<Edge> edges;
    private List<Integer> mstEdges;

    public KruskalMST(int[][] graph) {
        // 构建边集合，按照权重排序
        edges = new ArrayList<>();
        for (int i = 0; i < graph.length; i++) {
            for (int j = i + 1; j < graph[i].length; j++) {
                if (graph[i][j] != 0) {
                    edges.add(new Edge(i, j, graph[i][j]));
                }
            }
        }
        Collections.sort(edges);

        mstEdges = new ArrayList<>();
    }

    public void kruskal() {
        // 初始化所有顶点到无穷大作为并查集
        disjointSet dsu = new DisjointSet();

        // 按照权重从小到大遍历边，加入最小生成树直到连通所有顶点
        for (Edge edge : edges) {
            int u = dsu.find(edge.u);
            int v = dsu.find(edge.v);
            if (u != v) { // 如果它们不在同一集合中
                mstEdges.add(edge);
                dsu.union(u, v);
            }
            if (dsu.numSets == graph.length - 1) {
                break; // 找到了最小生成树，不再添加更多边
            }
        }
    }

    // 辅助类：并查集实现
    private static class DisjointSet {
        private int[] parents;

        public DisjointSet(int numVertices) {
            parents = new int[numVertices];
            for (int i = 0; i < numVertices; i++) {
                parents[i] = i;
            }
        }

        public int find(int vertex) {
            if (vertex != parents[vertex]) {
                parents[vertex] = find(parents[vertex]);
            }
            return parents[vertex];
        }

        public boolean union(int u, int v) {
            int rootU = find(u);
            int rootV = find(v);
            if (rootU == rootV) {
                return false; // 已经在同一集合中
            }
            parents[rootU] = rootV;
            return true;
        }

        public int numSets() {
            int count = 0;
            for (int i = 0; i < parents.length; i++) {
                if (i == parents[i]) {
                    count++;
                }
            }
            return count;
        }
    }

    // 使用方法
    public List<Edge> getMST() {
        kruskal();
        return mstEdges;
    }
}

在这个例子中，`KruskalMST` 类负责处理Kruskal算法的主要逻辑，包括构建边、排序和并查集操作。`DisjointSet` 是一个辅助类，实现了并查集数据结构。你可以通过创建 `KruskalMST` 对象，并调用 `getMST()` 获取最小生成树。