普利姆(Prim)算法

实际问题——修路问题

image-20241112171709616

有ABCDEFG七个村庄，修路使得村庄连通，同时要求修路公里数最小，问修路方案。

最小生成树

修路问题本质就是就是最小生成树问题， 先介绍一下最小生成树(Minimum Cost Spanning Tree)，简称MST。

  1. 给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树

  2. N个顶点，一定有N-1条边

  3. 包含全部顶点

  4. N-1条边都在图中

    image-20241112172040546

  5. 求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法

普利姆算法介绍

  1. 普利姆(Prim)算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有(n-1)条边包含所有n个顶点的连通子图，也就是所谓的极小连通子图

  2. 算法步骤：

    1. 设$G=(V,E)$是连通网，$T=(U,D)$是最小生成树，$V,U$是顶点集合，$E,D$是边的集合
    2. 若从顶点$u$开始构造最小生成树，则从集合V中取出顶点$u$放入集合$U$中，标记顶点$v$的$visited[u]=1$
    3. 若集合$U$中顶点$u_i$与集合$V-U$中的顶点$v_j$之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将顶点$v_j$加入集合$U$中，将边$(ui,vj)$加入集合$D$中，标记$visited[vj]=1$
    4. 重复步骤2，直到$U$与$V$相等，即所有顶点都被标记为访问过，此时$D$中有$n-1$条边

  3. 虽然步骤用了离散数学的术语显得抽象，但是图解很清晰：

    image-20241112202738570

    ∴最终修路：image-20241112203225175

  4. 为什么这种“每次 在已访问过的节点的基础上 选取最短的路径加入”能得到最短总路径呢？仔细想想，是因为修路问题的题目条件是——每个节点都必须连通，因此比如一开始选取了G，他就必须要和其他的某个村庄有联系，那么不妨就选取最短的那个，每次都这样找，总的修路路径就是最短的。

代码实现

PrimAlgorithm

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
package com.yukinoshita.algorithm.prim;

import java.util.Scanner;

public class PrimAlgorithm {
    private static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        int vertexNum = 7;
        char[] villages = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
//        int[][] weight = new int[vertexNum][vertexNum];
        int[][] weight = {
                {INF, 7, 7, INF, INF, INF, 6},
                {7, INF, INF, 9, INF, INF, 3},
                {7, INF, INF, INF, 8, INF, INF},
                {INF, 9, INF, INF, 7, 6, INF},
                {INF, INF, 8, 7, INF, 7, 4},
                {INF, INF, INF, 6, 7, INF, 4},
                {6, 3, INF, INF, 4, 4, INF}
        };
        
//        for(int i = 0; i < vertexNum; i++){
//            for(int j = 0; j < vertexNum; j++){
//                weight[i][j] = Integer.MAX_VALUE;//表示此路不通
//            }
//        }
        //输入各村庄之间的路径：
        //0-6 表示A-G，之后输入对应
//        int v1,v2,len=0;
//        Scanner sc = new Scanner(System.in);
//        System.out.println("输入地图数据:");//0 1 7 0 2 7 0 6 6 2 4 8 1 6 3 1 3 9 4 6 4 4 5 7 3 5 6 5 6 4 -1
//        while(true){
//            v1=sc.nextInt();
//            if(v1 == -1) break;
//            v2=sc.nextInt();
//            len=sc.nextInt();
//            weight[v1][v2] = len;
//            weight[v2][v1] = len;
//        }


        Graph graph = new Graph(vertexNum, villages, weight);
//        graph.showGraph();

        MinTree minTree = new MinTree();
        minTree.prim(graph, 6);

    }
}

//最小生成树
class MinTree {

    /**
     * 普利姆算法来创建最小生成树
     *
     * @param graph 图
     * @param v     开始构建的顶点
     */
    public void prim(Graph graph, int v) {
        boolean[] visited = new boolean[graph.vertexNum];
        visited[v] = true;

        //用v1，v2记录两个顶点的下标
        int v1 = -1;
        int v2 = -1;
        int minLen = Integer.MAX_VALUE;
        //因为有graph.vertexNum个顶点，所以prim算法结束应该有graph.vertexNum-1条边被记录
        for (int k = 0; k < graph.vertexNum - 1; k++) {

            //其实每一次就是在已访问过的节点的基础上，判断最短的路径并加入
            for (int i = 0; i < graph.vertexNum; i++) {         //访问过的节点    i
                for (int j = 0; j < graph.vertexNum; j++) {     //未访问过的节点   j
                    if (visited[i] && !visited[j] && graph.weight[i][j] < minLen) {
                        minLen = graph.weight[i][j];
                        v1 = i;
                        v2 = j;
                    }
                }
            }
            System.out.println("修路：" + graph.villages[v1] + "<--" + graph.weight[v1][v2] + "-->" + graph.villages[v2]);
            visited[v1] = true;
            visited[v2] = true;
            minLen = Integer.MAX_VALUE;

//            //其实每一次就是在已访问过的节点的基础上，判断最短的路径并加入
//            for(int i=0;i<graph.vertexNum;i++){         //访问过的节点    i
//                if(!visited[i]){//找到访问过的节点i
//                    continue;
//                }
//                for(int j=0;j<graph.vertexNum;j++){     //未访问过的节点   j
//                    if(visited[j]){//找到未访问过的节点j
//                        continue;
//                    }
//                    if(graph.weight[i][j] < minLen){
//                        minLen = graph.weight[i][j];
//                        v1 = i;
//                        v2 = j;
//                    }
//                }
//            }

        }
    }
}

class Graph {
    int vertexNum;//节点个数
    char[] villages;
    int[][] weight;//带权图

    Graph(int vertexNum, char[] villages, int[][] weight) {
        this.vertexNum = vertexNum;
        this.villages = villages;
        this.weight = weight;
    }

    void showGraph() {
        for (int i = 0; i < vertexNum; i++) {
            for (int j = 0; j < i; j++) {
                if (weight[i][j] != Integer.MAX_VALUE) {
                    System.out.println(villages[i] + "<--" + weight[i][j] + "-->" + villages[j]);
                }
            }
        }
    }
}