如何实现最小生成树算法？Kruskal算法实现

最小生成树算法是指在一个无向加权图中，找出一棵权值最小的生成树。常见的解决方案有两种：Prim算法和Kruskal算法。

Kruskal算法

Kruskal算法是一种基于并查集的算法，它将图中的所有边按照权值从小到大排序，并逐个加入生成树中。在加入每个边时，判断它所连的两个节点是否在同一个连通分量中，如果不在，则将它们合并。最终生成的就是一棵最小生成树。

下面是Kruskal算法的Java实现：

import java.util.*;

public class Kruskal {
    public static List<int[]> minimumSpanningTree(int[][] graph) {
        int n = graph.length;
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        List<int[]> edges = new ArrayList<>();
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(e -> e[2]));
        for (int u = 0; u < n; u++) {
            for (int v = u + 1; v < n; v++) {
                if (graph[u][v] != 0) {
                    queue.offer(new int[] {u, v, graph[u][v]});
                }
            }
        }
        while (!queue.isEmpty() && edges.size() < n - 1) {
            int[] edge = queue.poll();
            int u = edge[0], v = edge[1], w = edge[2];
            int pu = find(parent, u), pv = find(parent, v);
            if (pu != pv) {
                parent[pv] = pu;
                edges.add(edge);
            }
        }
        return edges;
    }

    private static int find(int[] parent, int u) {
        if (parent[u] != u) {
            parent[u] = find(parent, parent[u]);
        }
        return parent[u];
    }
}