数据结构与算法(36): 图- 最小生成树Prim

发表于   |   分类于

  Kruskal算法是一步步将森林中的树进行合并；而Prim算法是通过每次增加一条边来建立一棵树。

  Prim算法基本思想：首先选择任意一个顶点，从该顶点开始构造生成树；接下来要找出一条边添加到生成树，这需要枚举每一个树顶点到每一个非树顶点的所有边，然后找到最短边加入到生成树。重复以上步骤，直到所有顶点都加入到生成树中。

难点：如何找出下一个添加到树的边。

优化：使用邻接矩阵的时间复杂度$O(N^2)$，如果借助堆，每次选边的时间复杂度是$O(\log{E})$，然后用邻接表来存储图的话，整个算法的时间复杂度会降到$O(E\log{V})$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
public class Prim {
    public static void main(String[] args) {
        int vlen = 7;
        int[][] edges = {{1,3,11},{2,4,13},{3,5,3},{4,5,4},{1,2,6},{3,4,7},{0,1,1},{2,3,9},{0,2,2}};
        int[][] e = new int[vlen][vlen];
        int[] dis = new int[vlen];
        int inf = 9999;
        boolean[] book = new boolean[vlen];
        int count = 0;
        int sum = 0;
        // 初始化
        for (int i = 0; i < vlen; i++){
            for (int j = 0; j < vlen; j++){
                if (i == j){
                    e[i][j] = 0;
                }else {
                    e[i][j] = inf;
                }
            }
        }
        // 读入边
        for (int i = 0; i < edges.length; i++){
            e[edges[i][0]][edges[i][1]] = edges[i][2];
            // 无向图, 所以邻接矩阵将边反向再存储一遍
            e[edges[i][1]][edges[i][0]] = edges[i][2];
        }
        // 首先选择第一个顶点0加入生成树, 并初始化dis数组
        for (int i = 0; i < vlen; i++){
            dis[i] = e[0][i];
            book[i] = false;
        }
        book[0] = true;
        count++;
        // Prim算法核心
        while (count < vlen){
            int min = inf;
            int minIndex = 0;
            for (int i = 0; i < vlen; i++){
                if (!book[i] && dis[i] < min){
                    min = dis[i];
                    minIndex = i;
                }
            }
            book[minIndex] = true;
            count++;
            sum += dis[minIndex];
            // 再以minIndex为中间点, 扫描minIndex顶点的所有边, 更新生成树到每一个非树顶点的距离
            for(int k = 0; k < vlen; k++){
                if (!book[k] && dis[k] > e[minIndex][k]){
                    dis[k] = e[minIndex][k];
                }
            }
        }
        System.out.println("sum= " + sum);
    }
}