java最小生成树prim算法 代码

下面是使用 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);
    }
}

该代码使用邻接矩阵表示图，示例图的邻接矩阵为：

     2   3      6
  +--+---+--+---+--+
  | 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|
  +--+---+--+---+--+

输出结果为：

Edge    Weight
0 - 1   2
1 - 2   3
0 - 3   6
1 - 4   5