实现描述

如图：

Prim算法的基本思想是从一个顶点开始，逐步构建最小生成树。具体步骤如下：

1. 随机选取一个顶点作为起始点，并将其加入最小生成树的集合中。
2. 从该顶点出发，选择一条边连接到其他未被访问的顶点中的最小权值边。
3. 将该顶点加入到最小生成树的集合中，并标记为已访问。
4. 重复步骤2和步骤3，直到最小生成树包含所有顶点。

与Kruskal算法相比，Kruskal是选择最小边，通过判断连通性加入最小生成树；
Prim算法是选择点，构成最小生成树，然后选择未加入的点，通过权重判断是否能加入最小生成树；

下面是详细的构建过程：

首先加入index=0的点，此时最小生成树包含了只有0；

最小生成树此时节点[0],其他各个节点到最小生成树距离表：

之后，选择距离最小生成树距离最近的点加入，这里选择index=5,最小生成树此时节点[0,5],其他各个节点到最小生成树距离表：

注意，此时最小生成树节点[0,5]，是两个，这两个是一个整体；

依次类推，直至nodeInTheTree数组里面所有节点都加入，然后计算minDistance节点的和即为最小生成树边距离；

注意，如果需要获取加入的起点-终点的边情况，额外添加记录数组parents，当获取到本次加入最小生成树的节点时候，更新其他点连入最小生成树的边情况进行记录；

实现代码

public static void main(String[] args) {
        int nodeNum = 6;
        int[][] grid = {
                {0, 1, 5},
                {0, 5, 3},
                {0, 3, 7},
                {0, 2, 8},
                {1, 2, 4},
                {2, 5, 9},
                {3, 5, 6},
                {2, 3, 5},
                {3, 4, 5},
                {4, 5, 1}
        };
        int[][] matrix = new int[nodeNum][nodeNum]; // init matrix
        for (int i = 0; i < nodeNum; i++) {
            Arrays.fill(matrix[i], Integer.MAX_VALUE);
        }
        for (int i = 0; i < grid.length; i++) {
            int u = grid[i][0];
            int v = grid[i][1];
            int w = grid[i][2];
            matrix[u][v] = w;
            matrix[v][u] = w;
        }
        int[] minDistance = new int[nodeNum]; // 所有节点到最小生成树的最小距离
        Arrays.fill(minDistance, Integer.MAX_VALUE);
        boolean[] nodeInTheTree = new boolean[nodeNum]; //记录节点是否在最小生成树里面
        int[] parents = new int[nodeNum]; //记录最小生成树的边
        Arrays.fill(parents, -1);
        for (int i = 0; i < nodeNum; i++) {
            int current = 0; //默认0
            int minValue = Integer.MAX_VALUE;

            //选择距离当前生成树最近的点
            for (int j = 0; j < nodeNum; j++) {
                if (nodeInTheTree[j]) {
                    //在树中跳过
                    continue;
                }
                if (minDistance[j] < minValue) {
                    current = j;
                    minValue = minDistance[j];
                }
            }

            nodeInTheTree[current] = true;//将选择的节点加入最小生成树

            //更新其他节点到最小生成树的距离
            for (int j = 0; j < nodeNum; j++) {
                if (nodeInTheTree[j]) {
                    //在树中跳过
                    continue;
                }
                if (matrix[current][j] < minDistance[j]) {
                    minDistance[j] = matrix[current][j];
                    parents[j] = current;     //用最新选择的点去连接之前的点
                }
            }
        }
        int totalDistance = 0;
        for (int i = 1; i < nodeNum; i++) {
            totalDistance += minDistance[i];
        }

        System.out.println("总的权重值为：" + totalDistance);

        //输出边
        for (int i = 1; i < nodeNum; i++) {
            System.out.println("u=" + i + "; v=" + parents[i]);
        }

    }