目录

Prime算法

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

基本思想

对于图F而言,V是所有顶点的集合。现在,设置两个新的集合U和T, 其中U用于存放G的最小生成树中的顶点,T存放G的最小生成树的边。从所有$u\in U$,$v\in(V-U)$(V-U表示除去U的所有顶点)的边中选取权值最小的边(u,v),将顶点v加入集合U中,将边加入集合T中,如此不断重复,直到U=V为止,最小生成树构造完毕,这时集合T中包含了最小生成树的所有边。 https://gitee.com/lienhui68/picStore/raw/master/null/20200705034332.png 可以把prim算法理解为点优先

算法步骤

https://gitee.com/lienhui68/picStore/raw/master/null/20200705035504.png https://gitee.com/lienhui68/picStore/raw/master/null/20200705035556.png https://gitee.com/lienhui68/picStore/raw/master/null/20200705035628.png 依次类推直到U=V… https://gitee.com/lienhui68/picStore/raw/master/null/20200705035738.png

代码实现

 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
    /**
     * 处理未被访问过&相邻边权值最小的边
     *
     * @return -1 表示所有节点都被访问过了
     */
    private void buildMSTWithPrime() {

        visited[0] = true;
        int count = 0;
        while (true) {
            int min = Integer.MAX_VALUE;
            boolean changed = false;
            int s = -1, t = -1;
            // 访问过的顶点
            for (int i = 0; i < vertexNames.size(); i++) {
                if (!visited[i]) {
                    continue;
                }
                // 未被访问过 且 是有意义的边 , 排除和自己比较
                for (int j = 0; j < vertexNames.size(); j++) {
                    if (visited[j] || j == i || matrix[i][j] == Integer.MAX_VALUE) {
                        continue;
                    }

                    if (matrix[i][j] < min) {
                        s = i;
                        t = j;
                        min = matrix[i][j];
                        changed = true;

                    }

                }
            }
            if (changed) {
                // 保存连通信息
                edges[count++] = new Edge(s, t);
                // 将新顶点设置已访问
                visited[t] = true;
            } else {
                return;
            }
        }
    }

完整代码

  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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
package com.eh.ftd.dsa.ds;

import com.google.common.collect.Lists;

import java.util.List;

/**
 * Prime算法
 *
 * @author David Li
 * @create 2020/07/05 02:30
 */
public class Prime {
    /**
     * 图的邻接矩阵表现形式
     * 0表示自己指向自己,值为Integer.MAX_VALUE表示无穷远
     */
    private int[][] matrix;

    /**
     * 顶点的表现形式
     */
    private List<String> vertexNames;

    /**
     * 连通信息
     * k v 边
     */
    private Edge[] edges;

    class Edge {
        int s; // 边的起始坐标
        int t; // 边的末端坐标

        public Edge(int s, int t) {
            this.s = s;
            this.t = t;
        }
    }

    /**
     * 表示顶点是否被访问过, 如果是则表明已经加入到最小生成树中
     */
    private boolean[] visited;

    public Prime(List<String> vertexNames) {
        this.matrix = new int[vertexNames.size()][vertexNames.size()];
        this.vertexNames = vertexNames;
        edges = new Edge[vertexNames.size() - 1];
        visited = new boolean[vertexNames.size()];
        for (int i = 0; i < vertexNames.size(); i++) {
            for (int j = 0; j < vertexNames.size(); j++) {
                if (i != j) {
                    matrix[i][j] = Integer.MAX_VALUE;
                }
            }
        }
    }

    /**
     * 处理未被访问过&相邻边权值最小的边
     *
     * @return -1 表示所有节点都被访问过了
     */
    private void buildMSTWithPrime() {

        visited[0] = true;
        int count = 0;
        while (true) {
            int min = Integer.MAX_VALUE;
            boolean changed = false;
            int s = -1, t = -1;
            // 访问过的顶点
            for (int i = 0; i < vertexNames.size(); i++) {
                if (!visited[i]) {
                    continue;
                }
                // 未被访问过 且 是有意义的边 , 排除和自己比较
                for (int j = 0; j < vertexNames.size(); j++) {
                    if (visited[j] || j == i || matrix[i][j] == Integer.MAX_VALUE) {
                        continue;
                    }

                    if (matrix[i][j] < min) {
                        s = i;
                        t = j;
                        min = matrix[i][j];
                        changed = true;

                    }

                }
            }
            if (changed) {
                // 保存连通信息
                edges[count++] = new Edge(s, t);
                // 将新顶点设置已访问
                visited[t] = true;
            } else {
                return;
            }
        }

    }

    public void buildEdge(String v1, String v2, int weight) {
        int idx1 = getIndexByVertexName(v1);
        int idx2 = getIndexByVertexName(v2);
        matrix[idx1][idx2] = weight;
        matrix[idx2][idx1] = weight;
    }


    /**
     * 获取最小生成树权值和
     *
     * @return
     */
    public int getMinimumWeight() {
        int res = 0;
        for (Edge e : edges) {
            res += matrix[e.s][e.t];
        }
        return res;
    }

    /**
     * 打印最小生成树的连通信息
     */
    public void printPrimeMST() {

        for (Edge edge : edges) {
            System.out.printf("{%s,%s}", vertexNames.get(edge.s), vertexNames.get(edge.t));
        }
    }


    /**
     * 获得顶点对应下标
     *
     * @param vertexName
     * @return
     */
    private int getIndexByVertexName(String vertexName) {
        for (int i = 0; i < vertexNames.size(); i++) {
            if (vertexName.equals(vertexNames.get(i))) {
                return i;
            }
        }
        throw new RuntimeException();
    }


    public static void main(String[] args) {
        List cites = Lists.newArrayList("A", "B", "C", "D", "E", "F", "G");
        Prime prime = new Prime(cites);
        prime.buildEdge("A", "B", 12);
        prime.buildEdge("A", "F", 16);
        prime.buildEdge("A", "G", 14);
        prime.buildEdge("B", "C", 10);
        prime.buildEdge("B", "F", 7);
        prime.buildEdge("C", "D", 3);
        prime.buildEdge("C", "E", 5);
        prime.buildEdge("C", "F", 6);
        prime.buildEdge("D", "E", 4);
        prime.buildEdge("E", "F", 2);
        prime.buildEdge("E", "G", 8);
        prime.buildEdge("F", "G", 9);

        prime.buildMSTWithPrime();

        System.out.printf("最小生成树的权值和为: %d\n", prime.getMinimumWeight()); // 39
        System.out.println("最小生成树的连通信息:");
        prime.printPrimeMST();
    }
}

运行结果 https://gitee.com/lienhui68/picStore/raw/master/null/20200705083549.png