普里姆算法介绍

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

普利姆的算法如下:

1. 设G=(V,E)是连通网，T=(U,D)是最小生成树，V,U是顶点集合，E,D是边的集合

2. 若从顶点u开始构造最小生成树，则从集合V中取出顶点u放入集合U中，标记顶点v的visited[u]=1

3. 若集合U中顶点ui与集合V-U中的顶点vj之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将顶点 vj 加入集合 U 中，将边(ui,vj)加入集合 D 中，标记 visited[vj]=1

4. 重复步骤2，直到U与V相等，即所有顶点都被标记为访问过，此时D中有n-1条边

举例

1. 有七个站点 A,B,C,D,E,F,G，现在需要修线路把七个站点联通

2. 各个站点的距离用边线表示(权)，比如 A->C 为7公里

问： 如何修线路使各个站点都能联通， 同时修的线路里程最短？

image

求解思路

image

Java 代码实现

public class PrimAlgorithm {
    public static void main(String[] args) {
        // 7个顶点
        char[] data = new char[] { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
        int numOfVertex = data.length;
        // 邻接矩阵的关系使用二维数组表示,10000这个大数，表示两个点不联通
        int[][] weight = new int[][] { 
                { 10000, 5, 7, 10000, 10000, 10000, 2 }, 
                { 5, 10000, 10000, 9, 10000, 10000, 3 },
                { 7, 10000, 10000, 10000, 8, 10000, 10000 }, 
                { 10000, 9, 10000, 10000, 10000, 4, 10000 },
                { 10000, 10000, 8, 10000, 10000, 5, 4 }, 
                { 10000, 10000, 10000, 4, 5, 10000, 6 },
                { 2, 3, 10000, 10000, 4, 6, 10000 }, };
        // 从D开始     
        int startVertex = 3;    
        
        simplePrim(numOfVertex, data, weight, startVertex);
    }

    /**
     * 
     * @param numOfVertex      顶点的个数
     * @param data                    顶点的字符数组
     * @param adjacencyMatrix 邻接矩阵
     * @param v                          开始的顶点
     */
    public static void simplePrim(int numOfVertex, char[] data, int[][] adjacencyMatrix, int v) {
        // 存放哪个顶点被访问过
        int[] visited = new int[numOfVertex];
        
        // 把当前这个结点标记为已访问
        visited[v] = 1;
        
        // h1 和 h2 记录两个顶点的下标
        int h1 = -1;
        int h2 = -1;
        
        // 将 最小权重 初始成一个大数
        int minWeight = 10000; 
        // 普利姆算法结束后，有N个顶点， 那么就有N-1条边
        for (int k = 1; k < numOfVertex; k++) {
            // i 表示被访问过的顶点
            for (int i = 0; i < numOfVertex; i++) {
                // 当顶点被选中过，然后再去找与之有最小权值的另外一个顶点
                if(visited[i] == 1 ) {
                    // j 表示还没有选中过的顶点
                    for (int j = 0; j < numOfVertex; j++) {
                        if (visited[j] == 0 && adjacencyMatrix[i][j] < minWeight) {
                            // 寻找已经选中的顶点和未选中顶点间的权值最小的边
                            minWeight = adjacencyMatrix[i][j];
                            h1 = i;
                            h2 = j;
                        }
                    }
                }
            }
            // 找到一条权值最小的边
            System.out.println("边<" + data[h1] + "," + data[h2] + "> 权值:" + minWeight);
            // 将当前这个顶点标记为已经选中
            visited[h2] = 1;
            // minWeight 重新设置为最大值 10000
            minWeight = 10000;
        }
    }
}