[数据结构与算法]Kruskal算法（Java）

Prim算法和Kruskal算法都是从连通图中找出最小生成树的经典算法

从策略上来说，Prim算法是直接查找，多次寻找邻边的权重最小值，而Kruskal是需要先对权重排序后查找的

所以说，Kruskal在算法效率上是比Prim快的，因为Kruskal只需一次对权重的排序就能找到最小生成树，而Prim算法需要多次对邻边排序才能找到～

Prim算法的实现过程
首先以一个结点作为最小生成树的初始结点，然后以迭代的方式找出最小生成树中各结点权重最小的边，并加到最小生成树中。（加入之后如果产生回路了就要跳过这条边，选择下一个结点）当所有的结点都加入到最小生成树中后，就找出了这个连通图的最小生成树～

Kruskal算法的实现过程
Kruskal算法在找最小生成树结点之前，需要对权重从小到大进行排序。将排序好的权重边依次加入到最小生成树中（如果加入时产生回路就跳过这条边，加入下一条边），当所有的结点都加入到最小生成树中后，就找到了这个连通图的最小生成树。

Kruskal算法代码：

package Algorithm.kruskal;

import java.util.Arrays;

/**
 * 克鲁斯卡尔求图的最小生成树
 * 思路：先将边排序，从小到大生成最小生成树，在这个过程中不能形成回路。
 */
public class KruskalCase {

    private int edgeNum; //边的个数
    private char[] vertexs; // 顶点数组
    private int[][] matrix; // 邻接矩阵
    //使用 INF 表示两个顶点不能连通
    private static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {

        char[] vertexs = {'A','B','C','D','E','F','G'};

        int[][] matrix = {
                {0,12,INF,INF,INF,16,14},
                {12,0,10,INF,INF,7,INF},
                {INF,10,0,3,5,6,INF},
                {INF,INF,3,0,4,INF,INF},
                {INF,INF,5,4,0,2,8},
                {16,7,6,INF,2,0,9},
                {14,INF,INF,INF,8,9,0}
        };

        KruskalCase kruskalCase = new KruskalCase(vertexs,matrix);
        kruskalCase.print();
        EData[] edges = kruskalCase.getEdges();
        System.out.println("排序前："+ Arrays.toString(edges));
        kruskalCase.sortEdges(edges);
        System.out.println("排序后："+Arrays.toString(edges));

        kruskalCase.kruskal();
    }

    /**
     * 构造器
     * @param vertexs 顶点集合
     * @param matrix 邻接矩阵
     */
    public KruskalCase( char[] vertexs, int[][] matrix ) {
        int vlen = vertexs.length;
        //初始化顶点
        this.vertexs = new char[vlen];
        for ( int i = 0; i < vlen; i++ ) {
            this.vertexs[i] = vertexs[i];
        }

        //初始化边
        this.matrix = new int[vlen][vlen];
        for ( int i = 0; i < vlen; i++ ) {
            for ( int j = 0; j < vlen; j++ ) {
                this.matrix[i][j] = matrix[i][j];
            }
        }

        //统计边
        for ( int i = 0; i < vlen; i++ ) {
            for ( int j = i+1; j < vlen; j++ ) {
                if ( this.matrix[i][j] != INF ) {
                    edgeNum++;
                }
            }
        }

    }

    public void print() {
        System.out.println("邻接矩阵为：");
        for ( int i = 0; i < vertexs.length; i++ ) {
            for ( int j = 0; j < vertexs.length; j++ ) {
                System.out.printf("%20d",matrix[i][j]);
            }
            System.out.println();
        }

    }

    /**
     * 对所有边进行冒泡排序
     * @param edges 边的集合
     */
    private void sortEdges( EData[] edges ) {
        for ( int i = 0; i < edges.length - 1; i++ ) {
            for ( int j = 0; j < edges.length - i - 1; j++ ) {
                if ( edges[j].weight > edges[j+1].weight ){
                    EData temp = edges[j];
                    edges[j] = edges[j+1];
                    edges[j+1] = temp;
                }
            }
        }
    }

    /**
     * 返回顶点对应的下标
     * @param ch 顶点ch
     * @return 返回顶点ch对应的下标，找不到则返回-1
     */
    private int getPosition(char ch) {
        for (int i = 0; i < vertexs.length; i++){
            if (vertexs[i] == ch){
                return i;
            }
        }
        return -1;
    }

    /**
     * 从邻接矩阵中获取图中的所有边
     * @return
     */
    private EData[] getEdges() {
        int index = 0;
        EData[] edges = new EData[edgeNum];

        for (int i = 0; i < vertexs.length; i++){
            for (int j = i+1; j < vertexs.length; j++){
                if (matrix[i][j] != INF){
                    edges[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j] );
                }
            }
        }
        return edges;
    }

    /**
     * 获取下标为 i 的顶点的终点
     * @param ends
     * @param i
     * @return
     */
    private int getEnd(int[] ends, int i){
        while (ends[i] != 0){
            i = ends[i];
        }
        return i;
    }

    public void kruskal() {
        int index = 0; //表示最后结果数据的索引
        int[] ends = new int[edgeNum]; //用于保存在已有最小生成树中的顶点的终点
        //创建结果数组，保存最后的最小生成树
        EData[] rest = new EData[edgeNum];;

        //获取图中所有的边
        EData[] edges = getEdges();

        //按照边的权值大小进行排序
        sortEdges(edges);

        //添加边到最小生成树，并判断是否有回路
        for ( int i = 0; i < edgeNum; i++ ) {
            //获取第 i 条边的两个顶点
            int p1 = getPosition(edges[i].start);
            int p2 = getPosition(edges[i].end);

            //获取两个顶点在已有最小生成树中的终点
            int m = getEnd(ends,p1);
            int n = getEnd(ends,p2);

            if ( m != n ) {
                ends[m] = n;
                rest[index++] = edges[i];
            }
        }

        //统计并打印最小生成树
        for ( int i = 0; i < index; i++ ) {
            System.out.println(rest[i]);
        }

    }

}

/**
 * 创建一个类EData，它的对象实例就表示一条边
 */
class EData {
    char start;//边的起点
    char end;//边的另一端
    int weight;//边的权值

    public EData( char start, char end, int weight ) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "EData{" +
                "start=" + start +
                ", end=" + end +
                ", weight=" + weight +
                '}';
    }
}