Prim算法

示例练习>>>

prim 算法和 Kruskal 算法都是实现最小生成树的一种算法，prim 是通过点来实现，而 Kruskal 是通过边来实现，这节我们先讲 prim 算法。对于一个有 n 个顶点的无向图，如果只需要使用 n-1 条边即可把图中的所有点都连接起来，那么这 n 个顶点和这 n-1 条边构成的图就是生成树，如下图所示。

一个图的所有生成树中权值总和最少的就是最小生成树。 prim 算法就是求最小生成树的，他使用的是贪心算法。解题思路就是需要把图中的点分成两部分，一部分是已经选择的，我们用集合 S 记录，一部分是还没选择的，我们用集合 T 来记录。刚开始的时候集合 S 为空，集合 T 中包含图中的所有顶点，如下图所示，步骤如下。

• 第一步从集合 T 中任选一个顶点 v ，把顶点 v 放到集合 S 中。
• 更新集合 T 中和 v 相邻的顶点值。
• 继续从集合 T 中选择离集合 S 最近的顶点 v ，把它加入到集合 S 中，更新集合 T 中和 v 相邻的顶点值。
• 一直重复下去，直到集合 T 为空。

/**
 * @param g 图的邻接矩阵。
 * @return 返回最小生成树的值。
 */
private static int prim(int[][] g) {
    int n = g.length;// 图中顶点的个数。
    boolean[] visited = new boolean[n];
    // 没被选择的点到集合S的距离。
    int[] dis = new int[n];
    int max = 100;// 默认最大值。
    Arrays.fill(dis, max);// 刚开始的时候距离都默认最大值。
    visited[0] = true; // 选取顶点0作为起始点。
    for (int i = 0; i < n; i++)
        dis[i] = g[0][i];// 更新0到其他点的距离。
    int sum = 0;// 最小生成树的总的权值。
    // 继续查找 n-1 次。
    for (int i = 1; i < n; i++) {
        int v = -1;// 查找集合T中距离S的最小顶点v。
        int minDis = max;// 记录顶点v的值。
        for (int j = 0; j < n; j++) {// 查找。
            if (!visited[j] && (dis[j] < minDis)) {
                minDis = dis[j];
                v = j;
            }
        }
        System.out.print(v + ",");// 打印选择的点。
        visited[v] = true;// 把v加到集合S中，表示已经被选择了。
        sum += dis[v];// 累加总权值。
        for (int j = 0; j < n; j++) {// 更新集合T中和v邻接的顶点。
            if (!visited[j] && g[v][j] < dis[j])
                dis[j] = g[v][j];
        }
    }
    return sum;
}

更多