克鲁斯卡尔算法（Kruskal算法），是用来求加权连通图的最小生成树的算法

    基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。
    具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。

    普里姆算法和鲁斯卡尔算法的区别：
    (1)普里姆(Prim)算法思想：
    以某一顶点为起点，一点一点的去找各顶点上最小权值的边来构建最小生成树。图的存储结构是邻接矩阵，此方法需要一个顶点集合T，开始的时候为空集，慢慢的会将连通的顶点陆续的加入到集合中，全部顶点都加入集合以后，就得到我们所需要的最小生成树啦！
    (2)克鲁斯卡尔(Kruskal)算法思想：
    直接以边为目标，按照权值从小到大的顺序选择n-1条边来构建最小生成树，并且不能形成回路。图的存储结构采用的是边集数组，且权值相等的边在数组中的排列次序是任意的，如果图中的边数较多则此算法会很浪费时间！

    两者都是贪心策略追求最优解，但是Prim算法讲究全局优先，Kruskal算法讲究的是局部优先。

    1. /**
    2.  * 《Kruskal算法》
    3.  *     克鲁斯卡尔算法（Kruskal算法），是用来求加权连通图的最小生成树的算法
    4.  *
    5.  *  最佳应用-修路问题
    6.  *     胜利乡有7个村庄(A, B, C, D, E, F, G)，现在需要修路把7个村庄连通，各个村庄的距离用边线表示(权)，比如A–B距离5公里，问：如何修路保证各个村庄都能连通，并且总的修建公路总里程最短?
    7.  *
    8.  *                     5
    9.  *                【A】--【B】                          【A】  【B】
    10.  *              7 /  \   / \  9                      7 /  \   /
    11.  *               /  2 \ / 3 \                         /  2 \ / 3
    12.  *            【C】   【G】 【D】        ----->     【C】   【G】 【D】
    13.  *               \   4/ \6  /                             4/     /
    14.  *              8 \  /   \ / 4                            /     / 4
    15.  *                【E】--【F】                          【E】--【F】
    16.  *                     5                                    5
    17.  *  算法分析：
    18.  *   （1)边<A, G>权值2最小，加入到最小生成树结果中；
    19.  *   （2)上一步后，边<B, G>权值3最小，加入到最小生成树结果中；
    20.  *   （3)上一步后，边<E, G>权值4最小，加入到最小生成树结果中；
    21.  *   （4)上一步后，边<D, F>权值4最小，加入到最小生成树结果中；
    22.  *   （5)上一步后，边<A, B>权值5最小，但会和已有的边构成回路, 则跳过；
    23.  *   （6)上一步后，边<E, F>权值5最小，加入到最小生成树结果中；
    24.  *   （7)上一步后，边<F, G>权值6最小，但会和已有的边构成回路, 则跳过；
    25.  *   （8)上一步后，边<A, C>权值7最小，加入到最小生成树结果中;
    26.  *   （9)上一步后，边<C, E>权值8最小，但会和已有的边构成回路, 则跳过；
    27.  *   （10)上一步后，边<B, D>权值9最小，但会和已有的边构成回路, 则跳过；
    28.  */
    29. public class Kruskal {
    31.     /**
    32.      * 边的结构体
    33.      */
    34.     class Edge implements Comparable<Edge>{
    35.         // 边的开始结点
    36.         private String start;
    37.         // 边的结束结点
    38.         private String end;
    39.         // 边的权值
    40.         private Integer weight;
    42.         public Edge(String start, String end, Integer weight) {
    43.             this.start = start;
    44.             this.end = end;
    45.             this.weight = weight;
    46.         }
    48.         @Override
    49.         public String toString() {
    50.             return "Edge<" + start + ", " + end + ">[" + weight + "]";
    51.         }
    53.         @Override
    54.         public int compareTo(Edge o) {
    55.             return this.weight - o.weight;
    56.         }
    58.     }
    60.     /**
    61.      * Kruskal算法求最小生成树
    62.      * @param graph 村庄的图
    63.      * @return
    64.      */
    65.     public Integer minTree(ArrayGraph graph) {
    66.         Integer sumWeight = 0;
    67.         // 获取所有的边
    68.         Edge[] edges = getEdge(graph);
    69.         // 按权值从小到大排序
    70.         Arrays.sort(edges);
    71.         // 用于保存"已有最小生成树"中每个顶点对应的终点
    72.         int[] ends = new int[edges.length];
    73.         // 按顺序依次遍历所有的边
    74.         for (int i = 0; i < edges.length; i++) {
    75.             int p1 = graph.indexOfVertex(edges[i].start);
    76.             int p2 = graph.indexOfVertex(edges[i].end);
    77.             int m = getEnds(ends, p1);
    78.             int n = getEnds(ends, p2);
    79.             // 判断是否形成环路（判断该边的两个顶点的终点是否重合，重合的话则会构成回路）
    80.             if (m != n) {
    81.                 ends[m] = n;
    82.                 sumWeight += edges[i].weight;
    83.                 System.out.println("加入边："+  edges[i]);
    84.             }
    85.         }
    86.         return sumWeight;
    87.     }
    89.     /**
    90.      * 获取下标为i的顶点对应的终点
    91.      * @return
    92.      */
    93.     private int getEnds(int[] ends, int i) {
    94.         while (ends[i] != 0) {
    95.             i = ends[i];
    96.         }
    97.         return i;
    98.     }
    100.     /**
    101.      * 获取图的边集合
    102.      * @return
    103.      */
    104.     private Edge[] getEdge(ArrayGraph graph) {
    105.         int edgeNum = 0;
    106.         Edge[] edges = new Edge[graph.edgeSize()];
    107.         Object[][] array = graph.getEdgeArray();
    108.         for (int i = 0; i < array.length; i++) {
    109.             for (int j = i + 1; j < array[i].length; j++) {
    110.                 if (array[i][j] != null) {
    111.                     String start = (String)graph.getVertexOfIndex(i);
    112.                     String end = (String)graph.getVertexOfIndex(j);
    113.                     edges[edgeNum++] = new Edge(start, end, (Integer)array[i][j]);
    114.                 }
    115.             }
    116.         }
    117.         return edges;
    118.     }
    120.     public static void main(String[] args) {
    121.         ArrayGraph graph = new ArrayGraph(7);
    122.         // 添加顶点
    123.         graph.addVertex("A");
    124.         graph.addVertex("B");
    125.         graph.addVertex("C");
    126.         graph.addVertex("D");
    127.         graph.addVertex("E");
    128.         graph.addVertex("F");
    129.         graph.addVertex("G");
    130.         // 添加边
    131.         graph.addEdge("A", "B", 5);
    132.         graph.addEdge("A", "C", 7);
    133.         graph.addEdge("A", "G", 2);
    134.         graph.addEdge("B", "G", 3);
    135.         graph.addEdge("B", "D", 9);
    136.         graph.addEdge("C", "E", 8);
    137.         graph.addEdge("E", "F", 5);
    138.         graph.addEdge("E", "G", 4);
    139.         graph.addEdge("F", "G", 6);
    140.         graph.addEdge("D", "F", 4);
    141.         System.out.println("打印村庄的图:");
    142.         graph.print();
    144.         Kruskal kruskal = new Kruskal();
    145.         System.out.println("Kruskal算法求最小生成树：" + kruskal.minTree(graph));
    146.     }
    148. }