普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树(Minimum Cost Spanning Tree)，简称MST。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。

    最佳应用-修路问题
    胜利乡有7个村庄(A, B, C, D, E, F, G)，现在需要修路把7个村庄连通，各个村庄的距离用边线表示(权)，比如A–B距离5公里，问：如何修路保证各个村庄都能连通，并且总的修建公路总里程最短?
    普利姆（Prim）算法 - 图1

    普里姆算法的图解分析：
    普利姆（Prim）算法 - 图2

    1. /**
    2.  * 《Prim算法》
    3.  *     普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树(Minimum Cost Spanning Tree)，简称MST。意即由此算法搜索到的边子集所构成的树中，
    4.  *  不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。
    5.  *
    6.  *  最佳应用-修路问题
    7.  *     胜利乡有7个村庄(A, B, C, D, E, F, G)，现在需要修路把7个村庄连通，各个村庄的距离用边线表示(权)，比如A–B距离5公里，问：如何修路保证各个村庄都能连通，并且总的修建公路总里程最短?
    8.  *
    9.  *                     5
    10.  *                【A】--【B】                          【A】  【B】
    11.  *              7 /  \   / \  9                      7 /  \   /
    12.  *               /  2 \ / 3 \                         /  2 \ / 3
    13.  *            【C】   【G】 【D】        ----->     【C】   【G】 【D】
    14.  *               \   4/ \6  /                             4/     /
    15.  *              8 \  /   \ / 4                            /     / 4
    16.  *                【E】--【F】                          【E】--【F】
    17.  *                     5                                    5
    18.  *  算法分析：
    19.  *   （1）<A>顶点开始处理，选取权值最小的边A-G[2]  ==> <A,G>
    20.  *       A-C[7]、A-G[2]、A-B[5]
    21.  *   （2）<A,G>开始,将A和G顶点和他们相邻的还没有访问的顶点进行处理，选择G-B[3]  ==> <A,G,B>
    22.  *       A-C[7]、A-B[5]、G-B[3]、G-E[4]、G-F[6]
    23.  *   （3）<A,G,B>开始，将A,G,B 顶点和他们相邻的还没有访问的顶点进行处理，选择G-E[4] ==> <A,G,B,E>
    24.  *       A-C[7]、G-E[4]、G-F[6]、B-D[9]
    25.  *   （4）<A,G,B,E> 选择E-F[5]  ==> <A,G,B,E,F>
    26.  *   （5）<A,G,B,E,F> 选择F-D[4]  ==> <A,G,B,E,F,D>
    27.  *   （6）<A,G,B,E,F,D> 选择A-C[7]  ==> <A,G,B,E,F,D,C>
    28.  */
    29. public class Prim {
    31.     /**
    32.      * Prim算法求最小生成树
    33.      * @param graph 村庄的图
    34.      * @param vertex 图的开始顶点
    35.      * @return
    36.      */
    37.     public static Integer minTree(ArrayGraph graph, String vertex) {
    38.         Integer sumWeight = 0;
    39.         // 存放已选择的结点对应的索引
    40.         List<Integer> vertexList = new ArrayList<>();
    41.         // 放入开始结点的索引
    42.         vertexList.add(graph.indexOfVertex(vertex));
    43.         // 获取图中边的二维数组
    44.         Object[][] array = graph.getEdgeArray();
    45.         // 每一次遍历都会找到一个合适的结点
    46.         for (int i = 1; i < graph.size(); i++) {
    47.             Integer minVal = null;
    48.             Integer tempIndex = null;
    49.             // 从已选的结点中选取权值最小的边
    50.             for (Integer index : vertexList) {
    51.                 for (int j = 0; j < array.length; j++) {
    52.                     Integer weight = (Integer) array[index][j];
    53.                     if (weight != null && !vertexList.contains(j)) {
    54.                         if (minVal == null || weight < minVal) {
    55.                             minVal = weight;
    56.                             tempIndex = j;
    57.                         }
    58.                     }
    59.                 }
    60.             }
    61.             // 记录权值最小的结点
    62.             if (tempIndex != null) {
    63.                 sumWeight += minVal;
    64.                 vertexList.add(tempIndex);
    65.                 System.out.println("加入结点："+  graph.getVertexOfIndex(tempIndex));
    66.             }
    67.         }
    68.         return sumWeight;
    69.     }
    71.     public static void main(String[] args) {
    72.         ArrayGraph graph = new ArrayGraph(7);
    73.         // 添加顶点
    74.         graph.addVertex("A");
    75.         graph.addVertex("B");
    76.         graph.addVertex("C");
    77.         graph.addVertex("D");
    78.         graph.addVertex("E");
    79.         graph.addVertex("F");
    80.         graph.addVertex("G");
    81.         // 添加边
    82.         graph.addEdge("A", "B", 5);
    83.         graph.addEdge("A", "C", 7);
    84.         graph.addEdge("A", "G", 2);
    85.         graph.addEdge("B", "G", 3);
    86.         graph.addEdge("B", "D", 9);
    87.         graph.addEdge("C", "E", 8);
    88.         graph.addEdge("E", "F", 5);
    89.         graph.addEdge("E", "G", 4);
    90.         graph.addEdge("F", "G", 6);
    91.         graph.addEdge("D", "F", 4);
    92.         System.out.println("打印村庄的图:");
    93.         graph.print();
    95.         System.out.println("Prim算法求最小生成树：" + Prim.minTree(graph, "A"));
    96.     }
    98. }