最小生成树 Kruskal 算法

关于图的几个概念定义：（来自网上）

连通图：在无向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该无向图为连通图。
强连通图：在有向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该有向图为强连通图。
连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。
生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。
最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。

算法过程参考：https://blog.csdn.net/a2392008643/article/details/81781766

实现代码

image.png

以上图为例，实现算法：

/**
 * 科鲁斯特尔：求解最小生成树
 */
public class Kruskal {

    public int verticeSize; //图顶点个数
    public int[] vertices;  //图顶点集合
    public int[][] matrix;  //图的邻接矩阵
    public static int MAX_WEIGHT = 0xFFF8;

    Edge[] edges;        //最小生成树中所有边的集合
    int edgeSize;        //结合的大小

    public Kruskal(int verticeSize){
        this.verticeSize = verticeSize;
        matrix = new int[verticeSize][verticeSize];
        vertices = new int[verticeSize];
    }

    /**
     * 一条边
     */
    public static class Edge{
        public int start;
        public int end;
        public int weight;

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

    /**
     * 获取所有的边
     */
    private Edge[] getEdges(){
        int index = 0;
        Edge[] edges = new Edge[verticeSize * verticeSize]; //即便所有顶点之间都相连，边的个数不超过：verticeSize * verticeSize
        for (int i = 0; i < verticeSize; i++) {
            for (int j = 0; j < verticeSize; j++) {
                if (matrix[i][j] != 0 && matrix[i][j] != MAX_WEIGHT){
                    edges[index++] = new Edge(i,j,matrix[i][j]);
                }
            }
        }
        edgeSize = index;
        return edges;
    }

    /**
     * 对是所有的边进行排序，此时使用选择排序
     */
    private void sortEdge(Edge[] curEdges, int size){
        for (int i = 0; i < size; i++) {
            for (int j = i+1; j < size; j++) {
                if (curEdges[i].weight > curEdges[j].weight){
                    Edge temp = curEdges[i];
                    curEdges[i] = curEdges[j];
                    curEdges[j] = temp;
                }
            }
        }
    }

    public Edge[] kruskal(){
        int index = 0;

        //获取图的所有边
        edges = getEdges();

        //排序所有的边
        sortEdge(edges, edgeSize);

        //初始化 存储最短路径边的集合
        Edge[] rets = new Edge[verticeSize - 1];

        //存储所有 进入最短路径的 顶点的集合。
        //表示方式：下标用来表示起点,值表示终点。
        int[] flag = new int[verticeSize];

        //依次取出所有的边
        for (int i = 0; i < edgeSize; i++) {
            int start = edges[i].start;
            int end  = edges[i].end;

            int max1 = getEnd(flag, start);
            int max2 = getEnd(flag, end);

            // 如果 max1 和 max2 相等，则代表两个顶点已经在最短路径集合中，如果选中此边，则会造成回路。
            if(max1 != max2){
                rets[index++] = edges[i];
                if(max1 > max2){
                    int temp = max1;
                    max1 = max2;
                    max1 = temp;
                }
                flag[max1]= max2;
            }
        }

        return rets;
    }

    /**
     * 查看 对应索引的顶点，是否已经纳入最短路径之中。如果不在，直接返回当前索引； 如果存在返回所在路径中，顶点索引最大的索引值。
     */
    private int getEnd(int[] flag, int start) {
        while (flag[start] != 0){
            start = flag[start];
        }
        return start;
    }
}

    @Test
    public void test2(){
        Kruskal graph = new Kruskal(7);
        int[] v0 = new int[] {0, 50, 60, MAX_WEIGHT, MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT};
        int[] v1 = new int[] {50, 0, MAX_WEIGHT, 65, 40,MAX_WEIGHT,MAX_WEIGHT};
        int[] v2 = new int[] {60, MAX_WEIGHT, 0, 52, MAX_WEIGHT,MAX_WEIGHT,45};
        int[] v3 = new int[] {MAX_WEIGHT, 65, 52, 0, 50,30,42};
        int[] v4 = new int[] {MAX_WEIGHT, 40, MAX_WEIGHT, 50, 0,70,MAX_WEIGHT};
        int[] v5 = new int[] {MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 30,70,0,MAX_WEIGHT};
        int[] v6 = new int[] {MAX_WEIGHT, MAX_WEIGHT, 45, 42,MAX_WEIGHT,MAX_WEIGHT,0};
        graph.matrix[0] = v0;
        graph.matrix[1] = v1;
        graph.matrix[2] = v2;
        graph.matrix[3] = v3;
        graph.matrix[4] = v4;
        graph.matrix[5] = v5;
        graph.matrix[6] = v6;
        Kruskal.Edge[] rets = graph.kruskal();
        for (Kruskal.Edge ret : rets) {
            System.out.println(" v" + ret.start + " -  v" + ret.end + "  weight:  " + ret.weight);
         }
    }

结果：

 v3 -  v5  weight:  30
 v4 -  v1  weight:  40
 v3 -  v6  weight:  42
 v6 -  v2  weight:  45
 v4 -  v3  weight:  50
 v0 -  v1  weight:  50