Kruskals算法

Kruskal's算法是一种贪心算法，用于在加权无向图中找到最小生成树。它的思想是先将所有的边按照权重从小到大排序，然后从小到大加入边，直到生成树的边数达到节点数减一。在加入边的过程中，需要判断是否会形成环路，如果会，则不加入这条边。

Kruskal's算法的实现过程可以分为以下几个步骤：

1. 对所有的边按照权重从小到大排序。

2. 从小到大遍历每一条边，判断加入这条边是否会形成环路，如果不会则加入。

3. 重复步骤2，直到生成树的边数达到节点数减一。

以下是Kruskal's算法的Java代码实现：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

class Edge {
    int src, dest, weight;

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

class Graph {
    int V, E;
    ArrayList<Edge> edges;

    public Graph(int V, int E) {
        this.V = V;
        this.E = E;
        edges = new ArrayList<>(E);
    }

    public void addEdge(int src, int dest, int weight) {
        edges.add(new Edge(src, dest, weight));
    }

    public void kruskalMST() {
        ArrayList<Edge> result = new ArrayList<>();
        int[] parent = new int[V];
        for (int i = 0; i < V; i++) {
            parent[i] = i;
        }
        Collections.sort(edges, new Comparator<Edge>() {
            @Override
            public int compare(Edge e1, Edge e2) {
                return e1.weight - e2.weight;
            }
        });
        int i = 0, e = 0;
        while (e < V - 1) {
            Edge edge = edges.get(i++);
            int x = find(parent, edge.src);
            int y = find(parent, edge.dest);
            if (x != y) {
                result.add(edge);
                e++;
                parent[x] = y;
            }
        }
        System.out.println("Edges in Kruskal's MST:");
        for (Edge edge : result) {
            System.out.println(edge.src + " - " + edge.dest + ": " + edge.weight);
        }
    }

    private int find(int[] parent, int i) {
        if (parent[i] == i) {
            return i;
        }
        return find(parent, parent[i]);
    }
}

public class Main {
    public static void main(String[] args) {
        int V = 4;
        int E = 5;
        Graph graph = new Graph(V, E);
        graph.addEdge(0, 1, 10);
        graph.addEdge(0, 2, 6);
        graph.addEdge(0, 3, 5);
        graph.addEdge(1, 3, 15);
        graph.addEdge(2, 3, 4);
        graph.kruskalMST();
    }
}

这里定义了一个Edge类来表示边，一个Graph类来表示图。在Graph类中，kruskalMST()方法实现了Kruskal's算法。它首先将所有边按权值从小到大排序，然后遍历每条边，如果这条边所连接的两个顶点不在同一个集合中，就将它们合并，并将这条边加入结果集中。这里使用了一个find()方法来查找某个顶点所属的集合，并使用了路径压缩来优化查找的效率。

在Main类中，创建了一个包含5条边的图，然后调用kruskalMST()方法来计算最小生成树并输出结果。