图论-最小生成树kruskal算法（Java）

和prim算法以顶点为出发点不同，kruskal算法以边为中心，将所有边以小到大排序，遍历边，如果当前边的两个顶点有一个没有访问过，则记录该边，直到记录的边到达顶点数-1时，即所有顶点都可以相连，为最小生成树
实现代码：

    public static class Kruskal {
        private int verticeSize;// 顶点数量
        private int[] vertices; // 顶点数组
        private int[][] matrix; // 矩阵
        private int edgeSize;
        private static final int MAX = Integer.MAX_VALUE;
        private Edge[] edges;

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

        public void kruskal() {
            //存放排序边
            PriorityQueue<Edge> edgePriorityQueue = new PriorityQueue<>(new Comparator<Edge>() {
                @Override
                public int compare(Edge o1, Edge o2) {
                    return o1.weight - o2.weight;
                }
            });
            //遍历边
            for (int i = 0; i < verticeSize; i++) {
                for (int j = 0; j < verticeSize; j++) {
                    if (matrix[i][j] != 0 && matrix[i][j] != MAX) {
                        //加入队列
                        edgePriorityQueue.offer(new Edge(i, j, matrix[i][j]));
                    }
                }
            }

            //辅助数组 索引表示边的一段顶点，值为边的另一端顶点
            int[] edgeIndex = new int[verticeSize];
            //存放最小边
            Edge[] edges = new Edge[verticeSize - 1];
            int index = 0;
            while (!edgePriorityQueue.isEmpty()) {
                Edge edge = edgePriorityQueue.poll();
                //获取与顶点start相连的最远顶点
                int start = getEnd(edgeIndex, edge.start);
                //获取与顶点end相连的最远顶点
                int end = getEnd(edgeIndex, edge.end);

                if (start != end) {
                    if (start < end) {//我们用的是最远顶点，该判断保证有小到大指向的
                        edgeIndex[start] = end;
                    } else {
                        edgeIndex[end] = start;
                    }
                    edges[index++] = edge;
                } else {//最远顶点相同表示start和end已经相连了

                }

                if (index == verticeSize - 1) break;//都找到了
            }

            //输出
            int lengh = 0;
            for (int i = 0; i < index; i++) {
                lengh += edges[i].weight;
            }
            System.out.println("最小生成树的权值：" + lengh);
            char[] chars = new char[verticeSize];
            chars[0] = 'A';
            chars[1] = 'B';
            chars[2] = 'C';
            chars[3] = 'D';
            chars[4] = 'E';
            chars[5] = 'F';
            chars[6] = 'G';

            for (int i = 0; i < index; i++) {
                System.out.printf("(%s, %s)---> %d \n", chars[edges[i].start], chars[edges[i].end], matrix[edges[i].start][edges[i].end]);
            }
        }

        /**
         * 获取与顶点v相连的最远顶点
         *
         * @param edgeIndex
         * @param v
         * @return
         */
        private int getEnd(int[] edgeIndex, int v) {
            int ret = v;
            while (edgeIndex[ret] != 0) {
                ret = edgeIndex[ret];
            }
            return ret;
        }

        public static class Edge {
            int start;
            int end;
            int weight;

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

测试代码：

        Kruskal graph = new Kruskal(7);
        int[] v0 = new int[] {0, 50, 60, Kruskal.MAX, Kruskal.MAX,Kruskal.MAX,Kruskal.MAX};
        int[] v1 = new int[] {50, 0, Kruskal.MAX, 65, 40,Kruskal.MAX,Kruskal.MAX};
        int[] v2 = new int[] {60, Kruskal.MAX, 0, 52, Kruskal.MAX,Kruskal.MAX,45};
        int[] v3 = new int[] {Kruskal.MAX, 65, 52, 0, 50,30,42};
        int[] v4 = new int[] {Kruskal.MAX, 40, Kruskal.MAX, 50, 0,70,Kruskal.MAX};
        int[] v5 = new int[] {Kruskal.MAX, Kruskal.MAX, Kruskal.MAX, 30,70,0,Kruskal.MAX};
        int[] v6 = new int[] {Kruskal.MAX, Kruskal.MAX, 45, 42,Kruskal.MAX,Kruskal.MAX,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;

        graph.kruskal();

结果：
最小生成树的权值：257
(D, F)---> 30
(B, E)---> 40
(G, D)---> 42
(C, G)---> 45
(A, B)---> 50
(D, E)---> 50