用java写一个prim算法

下面是使用Java编写Prim算法的示例代码：

import java.util.*;

public class PrimAlgorithm {

    public static void prim(int[][] graph) {
        int numVertices = graph.length;
        int[] parent = new int[numVertices];
        int[] key = new int[numVertices];
        boolean[] mstSet = new boolean[numVertices];

        for (int i = 0; i < numVertices; i++) {
            key[i] = Integer.MAX_VALUE;
            mstSet[i] = false;
        }

        key[0] = 0;
        parent[0] = -1;

        for (int count = 0; count < numVertices - 1; count++) {
            int u = minKey(key, mstSet);
            mstSet[u] = true;

            for (int v = 0; v < numVertices; v++) {
                if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                    parent[v] = u;
                    key[v] = graph[u][v];
                }
            }
        }

        printMST(parent, graph);
    }

    public static int minKey(int[] key, boolean[] mstSet) {
        int min = Integer.MAX_VALUE;
        int minIndex = -1;

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

        return minIndex;
    }

    public static void printMST(int[] parent, int[][] graph) {
        System.out.println("Edge \tWeight");
        for (int i = 1; i < graph.length; i++) {
            System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
        }
    }

    public static void main(String[] args) {
        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(graph);
    }
}

在这个示例代码中，我们定义了一个 `prim` 函数，它接受一个二维数组 `graph` 作为输入，该数组表示无向图的邻接矩阵。该函数首先初始化了一些变量，然后从第一个顶点开始，逐步构建最小生成树，最后打印出最小生成树的边和权重。我们还定义了 `minKey` 和 `printMST` 函数来辅助实现 Prim 算法。在 `main` 函数中，我们创建了一个简单的无向图，并对其应用了 Prim 算法。