最小生成树java实现代码

最小生成树是指在一个加权无向图中，找到一棵包含所有顶点的树，并且它的边权重之和尽可能小。在Java中，最常用的算法实现是Prim算法和Kruskal算法。

**Prim算法** (也称为贪心策略) 的Java实现可以这样写：

import java.util.*;

class Prim {
    private int V; // 图的顶点数
    private List<Edge>[] adj; // 邻接表表示的邻接矩阵
    private boolean[] marked; // 标记已访问的节点
    private int minDistance[]; // 存储每个顶点到已构成树中的最短距离

    // 构建Prim算法所需的辅助函数
    private class Edge implements Comparable<Edge> {
        int src, dest, weight;

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

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

    // 主函数，输入邻接列表并返回最小生成树的总重量
    int primMST() {
        marked = new boolean[V];
        minDistance = new int[V];
        Arrays.fill(minDistance, Integer.MAX_VALUE);

        minDistance[0] = 0;
        int totalWeight = 0;

        for (int count = 0; count < V - 1; count++) {
            int u = findMinDistance();
            marked[u] = true;

            for (Edge edge : adj[u]) {
                int v = edge.dest;
                if (!marked[v] && edge.weight < minDistance[v]) {
                    minDistance[v] = edge.weight;
                }
            }
            totalWeight += minDistance[u];
        }

        return totalWeight;
    }

    // 找到未标记节点中距离当前生成树最近的一个
    int findMinDistance() {
        int min = Integer.MAX_VALUE, min_index = -1;
        for (int i = 0; i < V; i++) {
            if (!marked[i] && min > minDistance[i])
                min = minDistance[i], min_index = i;
        }
        return min_index;
    }

    // 添加边到邻接表
    void addEdge(int src, int dest, int weight) {
        adj[src].add(new Edge(src, dest, weight));
    }
}

// 示例：
public static void main(String args[]) {
    Prim graph = new Prim();
    int V = 5; // 图的顶点数
    graph.addEdge(0, 1, 10); // 边0-1，权重10
    graph.addEdge(0, 4, 6); // 边0-4，权重6
    graph.addEdge(1, 2, 8); // 边1-2，权重8
    graph.addEdge(1, 3, 7); // 边1-3，权重7
    graph.addEdge(2, 3, 9); // 边2-3，权重9
    graph.addEdge(3, 4, 5); // 边3-4，权重5

    System.out.println("Minimum spanning tree using Prim's algorithm has weight " + graph.primMST());
}

**Kruskal算法** 则是另一种选择，它通过从小到大顺序考虑所有边，并只加入不会形成环的边。以下是Kruskal算法的简化版：

class Kruskal {
    // ... (省略部分实现细节)
}

public static void main(String[] args) {
    Kruskal kruskal = new Kruskal();
    // 添加边到森林中...
    int mstWeight = kruskal.buildMST(); // 建立最小生成树
    System.out.println("Minimum spanning tree using Kruskal's algorithm has weight " + mstWeight);
}