Java语言实现最小生成树算法（Minimum Spanning Tree）

Java语言实现最小生成树算法（Minimum Spanning Tree）

在Java中实现最小生成树（Minimum Spanning Tree, MST）算法，同样可以使用Kruskal算法或Prim算法。以下是使用Kruskal算法实现MST的示例代码。

Kruskal算法

Kruskal算法的主要思想是将所有边按照权重从小到大排序，然后逐一添加到生成树中，如果添加一条边会形成环，则跳过这条边，直到生成树中包含所有顶点。

示例代码：

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

// 边类
class Edge {
    int from, to, weight;

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

// 并查集类
class UnionFind {
    private int[] parent, rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
}

// Kruskal算法类
public class KruskalMST {

    public static List<Edge> kruskal(List<Edge> edges, int n) {
        Collections.sort(edges, Comparator.comparingInt(edge -> edge.weight));

        UnionFind uf = new UnionFind(n);
        List<Edge> mst = new ArrayList<>();

        for (Edge edge : edges) {
            if (uf.find(edge.from) != uf.find(edge.to)) {
                uf.union(edge.from, edge.to);
                mst.add(edge);
            }
        }
        return mst;
    }

    public static void main(String[] args) {
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 10));
        edges.add(new Edge(0, 2, 6));
        edges.add(new Edge(0, 3, 5));
        edges.add(new Edge(1, 3, 15));
        edges.add(new Edge(2, 3, 4));
        int n = 4; // 节点数

        List<Edge> mst = kruskal(edges, n);
        System.out.println("Minimum Spanning Tree:");
        for (Edge edge : mst) {
            System.out.println("from " + edge.from + " to " + edge.to + ", weight: " + edge.weight);
        }
    }
}