思路

构建一个一维数组，用于记录某一个节点是否被包含

构建一个一维数组，用于记录未包含的节点到已包含节点的最小花费

初始化从第一个节点开始，将其设为被包括，对于剩余节点标记为未包含，且到达的最低花费为节点1到达的花费 (此时被包括的只有节点1)

• i：表示遍历的节点 [1, n)
  • k：表示未被包括的节点 [2, n)
    • 找到未被包含的最低消费的节点
  • 将未被包含的最低节点标记为包含
  • 将新增的节点到各个未包含节点的花费与原先的最低花费表作对比，若有更优的花费则更新

代码

public static void prim(int n, int[][] c) {
    boolean[] isInclude = new boolean[n + 1];
    int[] lowCost = new int[n + 1];
    int[] closest = new int[n + 1];

    // 以第一个为节点开始
    isInclude[1] = true;
    // 初始化后续的每个节点都标记为未包括，最低花费为节点1到各点的花费，最近节点为1
    for (int i = 2; i < n; ++i) {
        isInclude[i] = false;
        lowCost[i] = c[1][i];
        closest[i] = 1;
    }

    for (int i = 1; i < n; ++i) {
        int min = Integer.MAX_VALUE;
        int j = 1;
        // 找到到未包含的节点的最小花费
        for (int k = 2; k < n; ++k) {
            if (lowCost[k] < min && !isInclude[k]) {
                min = lowCost[k];
                j = k;
            }
        }
        isInclude[j] = true;
        System.out.println(j + ", " + closest[j]);

        // 更新到达未包含节点的最小花费
        for (int k = 2; k <= n; ++k) {
            // 若新加入的节点到其余未加入的节点的花费超过目前的最低最低花费，则更新
            if (c[j][k] < lowCost[k] && !isInclude[k]) {
                lowCost[k] = c[j][k];
                closest[k] = j;
            }
        }
    }
}