克鲁斯克拉算法（Kruskal）解决最小数生成

这个问题可以解决几个村庄之间修路的问题，比如有A,B,C,D,E,F,G这7个村庄和其中一些村庄的路程距离问题，这个时候需要在这几个村庄之间修路，这条路必须可以使每一个村庄能够达到其他村庄，并且这条路的总距离最短，对于这个问题我们可以将已经告诉的村庄的距离进行排序，然后从里面从小到大取出一条路，如果取出来的这条路和已经选取的路没有构成回路（这里判断思路优点难以理解），则加入结果集，直到取出所有的路段

public class KruskalTest {
    public static void main(String[] args) {
        int INF = Integer.MAX_VALUE;
        char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] edges = {
                {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   },
        };
        MinTree minTree = new MinTree(vertexs,edges);
        minTree.generateMinTree();
        minTree.showMinTree();
    }
}
class MinTree{
    private int verCount; //定点总数
    private int edgeCount; //路段总数
    private char[] vertexs; //定点集合
    private int[][] edges; //初识邻接矩阵
    private List<EData> allEdge;  //所有路段
    private List<EData> res;  //结果集路段
    private int[] ends; //这个是判断有没有构成回路的数组

    public MinTree(char[] vertexs, int[][] edges) {
        this.vertexs = vertexs;
        this.edges = edges;
        verCount = vertexs.length;
        allEdge = new ArrayList<>();
        res = new ArrayList<>();
        ends = new int[verCount];
        for(int i = 0; i < verCount; i++){ //将路段添加道级和，便于操作
            for(int j=0; j < i; j++){
                allEdge.add(new EData(j, i, edges[i][j]));
            }
        }
        edgeCount = allEdge.size();
        Collections.sort(allEdge);
    }

    public void generateMinTree(){
        for (int i = 0; i < edgeCount; i++) {
            int first = allEdge.get(i).start;
            int second = allEdge.get(i).end;

            int firstEnd = getEnd(first);
            int secondEnd = getEnd(second);
            if(firstEnd != secondEnd){ //如果两个顶点的最远距离不同，则不会构成回路
                res.add(allEdge.get(i));
                ends[firstEnd] = secondEnd; //这里其实和我们构建路段EData有关系的，添加到集合的路段里start总数较小的字母，而end总是较大的字母，再根据getEnd函数进行分析，如果一条路段将添加到结果集，则start总是较小的字母，所以较小的字母（start）的最远路程应该是较大字母（end）最远距离
                System.out.println("-----");
            }
            System.out.println("EData{<" + vertexs[first] + ", " + vertexs[second] + "> = " + allEdge.get(i).weight + '}');
        }
    }

    public void showMinTree(){
        for (int i = 0; i < res.size(); i++) {
            System.err.println("EData{<" + vertexs[res.get(i).start] + ", " + vertexs[res.get(i).end] + "> = " + res.get(i).weight + '}');
        }
    }
    private int getEnd(int endIndex){ //获取一个定点的最远路程，不是说距离的大小，而是说A,B,C,D,E,F,G,比如说A达到了F，而C达到了G，则C的最远路程最远，也可以看成离终点最近
        while (ends[endIndex] != 0){ //，刚开始A点的最远距离可能是B，而B点的最远距离是F，则A点的最远距离就是F
            endIndex = ends[endIndex];
        }
        return endIndex;
    }
}
class EData implements Comparable<EData>{ //边（路段）对象
    public int start;
    public int end;
    public int weight;

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

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

    @Override
    public int compareTo(EData o) {
        return this.weight - o.weight;
    }
}