prim算法 java实现

很高兴为您解答，以下是Prim算法的Java实现示例（假设有一张无向图，顶点数为n，用邻接矩阵G表示）：

public class PrimAlgorithm {

    public void prim(int[][] G) {
        int n = G.length; // 顶点数
        int[] lowcost = new int[n]; // 存储最小权值
        int[] closest = new int[n]; // 存储最近邻居

        // 初始化数组
        for (int i = 1; i < n; i++) {
            lowcost[i] = G[0][i];
            closest[i] = 0;
        }

        // 从剩余的n-1个节点中选择n-1条边
        for (int i = 1; i < n; i++) {
            int minVal = Integer.MAX_VALUE;
            int k = 0;
            // 找出lowcost中最小的边
            for (int j = 1; j < n; j++) {
                if (lowcost[j] != 0 && lowcost[j] < minVal) {
                    minVal = lowcost[j];
                    k = j;
                }
            }
            // 输出最小边的两个顶点
            System.out.println("(" + closest[k] + ", " + k + ")");
            lowcost[k] = 0; // 标记k为已访问
            // 更新lowcost和closest数组
            for (int j = 1; j < n; j++) {
                if (lowcost[j] != 0 && G[k][j] < lowcost[j]) {
                    lowcost[j] = G[k][j];
                    closest[j] = k;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[][] G = {
            {0, 28, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 10, Integer.MAX_VALUE},
            {28, 0, 16, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 14},
            {Integer.MAX_VALUE, 16, 0, 12, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE},
            {Integer.MAX_VALUE, Integer.MAX_VALUE, 12, 0, 22, Integer.MAX_VALUE, 18},
            {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 22, 0, 25, 24},
            {10, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 25, 0, Integer.MAX_VALUE},
            {Integer.MAX_VALUE, 14, Integer.MAX_VALUE, 18, 24, Integer.MAX_VALUE, 0}
        };
        PrimAlgorithm pa = new PrimAlgorithm();
        pa.prim(G);
    }
}

其中，数组lowcost用来存储最小权值，closest用来存储最近邻居。算法的基本思路是从第一个节点开始，每次找到距离它最近的且还未被访问的节点k，并输出与之相连的最小边，将k标记为已访问，并更新lowcost和closest数组。重复上述操作，直到所有节点都已被访问。