贪心算法_最小生成树_Prim（普里姆）算法

/** * 7.贪心算法_最小生成树_Prim（普里姆）算法 * @author Matt */
public class Prim {
    /** * 普里姆算法 * @param n 节点个数 * @param c 权值数组 */
    public static void prim(int n, float [][]c) {
        float[] lowcost = new float[n+1]; // 保存权值最小的边
        int[] closest = new int[n+1]; // 保存邻接点的权值
        boolean[] s = new boolean[n+1]; // 判断是否通过

        s[1] = true; // 第一个点通过
        for (int i = 2; i <= n; i++) {
            // 将1的所有邻接点的权值存入lowcost，用于下面查找
            lowcost[i] = c[1][i];
            // 设置1的所有临接点的权值为1，初始化
            closest[i] = 1;
            s[i] = false;
        }
        // 从第1个节点到n-1个节点，因为到最后一个时节点已经全部走过了
        for (int i = 1; i < n; i++) {
            float min = Float.MAX_VALUE; // 取浮点型的最大值
            int j = 1; 
            for (int k = 2; k <= n; k++) {
                // 找出当前节点的最小邻接边（lowcost中的最小值）
                // 注意：前面第一个节点中的lowcost均为1，这是
                // 初始化的结果，lowcost的设置在下面一个循环
                // 并且当前节点没有走过（s中为false）
                if ((lowcost[k] < min) && (!s[k])) {
                    // 令最小值为最短邻接边（lowcost中的最小值）
                    min = lowcost[k]; 
                    j = k; // 权值最小的邻接点的坐标覆盖j
                }
            }
            // 打印路径
            System.out.println(closest[j] + ", " + j);
            s[j] = true; // 走过的节点设置为true
            // 从当前节点j=1为前节点，后节点从2到n开始遍历
            for (int k = 2; k <= n; k++) {
                // 找出最小的邻接点的权值赋值进lowcost中
                // 顺应上面的循环，并且下一个节点没有走过
                if ((c[j][k] < lowcost[k]) && (!s[k])) {
                    // 为lowcost赋值
                    lowcost[k] = c[j][k];
                    // 设置离k最近的节点为j，赋值进数组
                    closest[k] = j;
                }
            }
        }
    }

    public static void main(String[] args) {
        int n = 6;
        float m = Float.MAX_VALUE;
        float[][] c = { {0, 0, 0, 0, 0, 0},  
                   {0, m, 6, 1, 5, m, m},  
                   {0, 6, m, 5, m, 3, m},  
                   {0, 1, 5, m, 5, 6, 4},  
                   {0, 5, m, 5, m, m, 2},  
                   {0, m, 3, 6, m, m, 6},
                   {0, m, m, 4, 2, 6, m} };
        prim(n, c);

    }

}
// 运行结果：
// 1, 3
// 3, 6
// 6, 4
// 3, 2
// 2, 5