最小生成树 代码

下面我将为您提供 Prim 算法和 Kruskal 算法的 Java 代码实现。

### Prim 算法

import java.util.Arrays;

public class PrimMST {

    private static final int V = 5; // 图中顶点的数量

    // 查找最小权值的顶点
    private int minKey(int[] key, boolean[] mstSet) {
        int min = Integer.MAX_VALUE;
        int minIndex = -1;

        for (int i = 0; i < V; i++) {
            if (!mstSet[i] && key[i] < min) {
                min = key[i];
                minIndex = i;
            }
        }

        return minIndex;
    }

    // 打印生成的 MST
    private void printMST(int[] parent, int[][] graph) {
        System.out.println("Edge \tWeight");
        for (int i = 1; i < V; i++) {
            System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
        }
    }

    // 使用 Prim 算法查找 MST
    private void primMST(int[][] graph) {
        int[] parent = new int[V]; // 存储 MST
        int[] key = new int[V]; // 存储每个顶点的键值
        boolean[] mstSet = new boolean[V]; // 判断顶点是否已经在 MST 中

        // 初始化 key 为最大值，mstSet 为 false
        Arrays.fill(key, Integer.MAX_VALUE);
        Arrays.fill(mstSet, false);

        // 将第一个顶点加入 MST
        key[0] = 0;
        parent[0] = -1;

        // 一共需要添加 V-1 个顶点到 MST 中
        for (int i = 0; i < V - 1; i++) {
            // 选择最小键值的顶点
            int u = minKey(key, mstSet);

            // 将该顶点加入 MST
            mstSet[u] = true;

            // 更新相邻顶点的键值
            for (int v = 0; v < V; v++) {
                if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                    parent[v] = u;
                    key[v] = graph[u][v];
                }
            }
        }

        // 打印生成的 MST
        printMST(parent, graph);
    }

    public static void main(String[] args) {
        PrimMST prim = new PrimMST();
        int[][] graph = new int[][]{{0, 2, 0, 6, 0},
                                     {2, 0, 3, 8, 5},
                                     {0, 3, 0, 0, 7},
                                     {6, 8, 0, 0, 9},
                                     {0, 5, 7, 9, 0}};

        prim.primMST(graph);
    }
}

### Kruskal 算法

import java.util.Arrays;

public class KruskalMST {

    private static class Edge implements Comparable<Edge> {
        int src, dest, weight;

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

    private static final int V = 5; // 图中顶点的数量
    private int[] parent; // 存储 MST
    private Edge[] edges; // 存储图中所有边

    // 初始化 parent 数组
    private void makeSet() {
        parent = new int[V];
        for (int i = 0; i < V; i++) {
            parent[i] = i;
        }
    }

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

    // 合并节点 x 和 y 所在的集合
    private void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        parent[rootX] = rootY;
    }

    // 打印生成的 MST
    private void printMST() {
        System.out.println("Edge \tWeight");
        for (Edge edge : edges) {
            System.out.println(edge.src + " - " + edge.dest + "\t" + edge.weight);
        }
    }

    // 使用 Kruskal 算法查找 MST
    private void kruskalMST(int[][] graph) {
        makeSet(); // 初始化 parent 数组
        edges = new Edge[V * (V - 1) / 2]; // 初始化 edges 数组

        int index = 0;
        for (int i = 0; i < V; i++) {
            for (int j = i + 1; j < V; j++) {
                if (graph[i][j] != 0) {
                    edges[index++] = new Edge(i, j, graph[i][j]);
                }
            }
        }

        Arrays.sort(edges); // 将边按照权值从小到大排序

        Edge[] mst = new Edge[V - 1]; // 存储 MST 的边

        int count = 0;
        index = 0;
        while (count < V - 1) {
            Edge edge = edges[index++];

            int x = find(edge.src);
            int y = find(edge.dest);

            if (x != y) {
                mst[count++] = edge;
                union(x, y);
            }
        }

        // 打印生成的 MST
        printMST();
    }

    public static void main(String[] args) {
        KruskalMST kruskal = new KruskalMST();
        int[][] graph = new int[][]{{0, 2, 0, 6, 0},
                                     {2, 0, 3, 8, 5},
                                     {0, 3, 0, 0, 7},
                                     {6, 8, 0, 0, 9},
                                     {0, 5, 7, 9, 0}};

        kruskal.kruskalMST(graph);
    }
}

以上两份代码分别实现了 Prim 算法和 Kruskal 算法。其中，Prim 算法使用的是邻接矩阵表示图，而 Kruskal 算法则使用的是边列表。在实际应用中，具体使用哪种算法取决于图的规模、密度以及应用场景等因素。