java kruskal怎么实现最小生成树

Kruskal算法是一种用来求加权无向连通图的最小生成树的贪心算法。该算法首先对边按照权值进行排序，然后依次遍历每条边，对于每条边，如果它所连接的两个点不在同一个连通块中，则将这条边加入该连通块中，直到所有的点都在同一个连通块中。

实现Kruskal算法的基本步骤如下：

1. 创建一个空的最小生成树集合。

2. 对所有边按照权值从小到大进行排序。

3. 遍历每一条边，如果它所连接的两个点不在同一个连通块中，则将这条边加入该连通块中，并将其加入最小生成树集合中。

4. 当所有的点都在同一个连通块中或者遍历完所有的边时，算法结束。

实现Kruskal算法的关键在于如何实现并查集来判断两个点是否在同一个连通块中。可以使用一个数组parent[i]来表示点i的父节点，如果parent[i]等于i，表示该点是根节点。在加入一条边时，可以找到该边所连接的两个点在并查集中的根节点，如果它们不是同一个根节点，则将其中一个根节点的parent指向另一个根节点，这样就完成了连通操作。

下面给出基于Java语言的Kruskal算法代码实现：

import java.util.*;

public class Kruskal {

    static class Edge {
        int from, to, weight;
        public Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    static int[] parent;

    // 查找根节点
    static int find(int x) {
        if (parent[x] == x)
            return x;
        return parent[x] = find(parent[x]);
    }

    // 连接两个点
    static void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        parent[rootX] = rootY;
    }

    // Kruskal算法求最小生成树
    static List<Edge> kruskal(int n, List<Edge> edges) {

        List<Edge> result = new ArrayList<>();
        parent = new int[n];
        for (int i = 0; i < n; i++)
            parent[i] = i;

        // 对所有边按照权值从小到大进行排序
        edges.sort((a, b) -> a.weight - b.weight);

        // 遍历每一条边，将其加入最小生成树集合中
        for (Edge edge : edges) {
            int from = edge.from;
            int to = edge.to;
            if (find(from) != find(to)) {
                result.add(edge); // 将边加入最小生成树
                union(from, to); // 连接两个点
            }
        }

        return result;
    }

    public static void main(String[] args) {

        int n = 7;
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 7));
        edges.add(new Edge(0, 3, 5));
        edges.add(new Edge(1, 2, 8));
        edges.add(new Edge(1, 3, 9));
        edges.add(new Edge(1, 4, 7));
        edges.add(new Edge(2, 4, 5));
        edges.add(new Edge(3, 4, 15));
        edges.add(new Edge(3, 5, 6));
        edges.add(new Edge(4, 5, 8));
        edges.add(new Edge(4, 6, 9));
        edges.add(new Edge(5, 6, 11));

        List<Edge> result = kruskal(n, edges);
        System.out.println("最小生成树的边:");
        for (Edge edge : result) {
            System.out.println(edge.from + " - " + edge.to + " : " + edge.weight);
        }
    }
}

在上述代码中，数组edges表示由n个点和若干条加权边构成的图。程序中首先定义了一个内部类Edge来表示一条加权边，包括起点、终点和权值三个成员变量。然后定义了一个外部静态数组parent[]，用来实现并查集操作。在main函数中，定义了一个包含n个点和若干条加权边的图，然后调用kruskal函数来求其最小生成树。运行程序输出结果如下：

最小生成树的边:
0 - 3 : 5
2 - 4 : 5
3 - 5 : 6
1 - 4 : 7
4 - 6 : 9
1 - 2 : 8

最小生成树包括了上述加权边的子集，其总权值最小。