算法-最小生成树算法(克鲁斯卡尔算法 Kruskal`s algorithm)_kruskal minimum cost spanning tree algorithm

概述

• 克鲁斯卡尔算法(Kruskal`s algorithm)也是求最小生成树的算法, 也就是在包含 n个顶点的带权无向连通图中, 找出(n-1)条边的最小耗费生成树(Minimum Cost Spanning Tree), 简称 MST
• 克鲁斯卡尔算法的时间复杂度为 O(eloge) e为网中的边数
• 基本思想: 将所有的边, 按照权值从小到大进行排序, 并保证边的终点不构成回路(指每个边的终点不允许重合)

公交站问题

• 某城市有7个居民区(A,B,C,D,E,F,G), 需要在各区建一个公交站点连通. 各个村庄的距离用边线权值来表示, 比如 A-B距离12公里
• 需要保证各个区都能连通, 且连通的总里程为最短

• 求出最小生成树的步骤:

• 代码实现

public class KruskalAlgorithmApp {
    /** 边的总个数*/
    private int edgeCount;
    /** 顶点数组*/
    private char[] vertexes;
    /** 邻接矩阵*/
    private int[][] matrix;
    /** 定义常量, 9999表示某顶点间不连通*/
    private static final int INF = 9999;
    public static void main(String[] args) {
        char[] vertexes = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        /** 设置邻接矩阵的顶点与顶点间的边(附带权值)*/
        int matrix[][] = {
                       /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
                /*A*/ {   0,  12, INF, INF, INF,  16,  14},
                /*B*/ {  12,   0,  10, INF, INF,   7, INF},
                /*C*/ { INF,  10,   0,   3,   5,   6, INF},
                /*D*/ { INF, INF,   3,   0,   4, INF, INF},
                /*E*/ { INF, INF,   5,   4,   0,   2,   8},
                /*F*/ {  16,   7,   6, INF,   2,   0,   9},
                /*G*/ {  14, INF, INF, INF,   8,   9,   0}
        };
        KruskalAlgorithmApp mst = new KruskalAlgorithmApp(vertexes, matrix);
        /** 打印邻接矩阵*/
        mst.print();
        /** 求出最小生成树*/
        mst.kruskal();
    }

    /** 定义边类(一个实例表示一条边)*/
    class Edge {
        /** 指定边的第1个顶点*/
        char start;
        /** 指定边的第2个顶点*/
        char end;
        /** 指定边的权值*/
        int weight;

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

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

    public KruskalAlgorithmApp(char[] vertexes, int[][] matrix) {
        /** 初始化顶点个数*/
        int vertexCount = vertexes.length;
        /** 初始化顶点*/
        this.vertexes = new char[vertexCount];
        for(int i = 0; i < vertexCount; i++) {
            this.vertexes[i] = vertexes[i];
        }
        /**初始化边*/
        this.matrix = new int[vertexCount][vertexCount];
        for(int i = 0; i < vertexCount; i++) {
            for(int j= 0; j < vertexCount; j++) {
                this.matrix[i][j] = matrix[i][j];
            }
        }
        /** 统计边的条数*/
        for(int i =0; i < vertexCount; i++) {
            for(int j = i+1; j < vertexCount; j++) {
                if(this.matrix[i][j] != INF) {
                    edgeCount++;
                }
            }
        }
    }

    /** 打印邻接矩阵*/
    public void print() {
        System.out.println("邻接矩阵为:");
        for(int i = 0; i < vertexes.length; i++) {
            for(int j = 0; j < vertexes.length; j++) {
                System.out.printf("%6d", matrix[i][j]);
            }
            System.out.println();
        }
    }

    /** 通过冒泡排序算法将边从小到大排序*/
    private void sortEdges(Edge[] edges) {
        for(int i = 0; i < edges.length - 1; i++) {
            for(int j = 0; j < edges.length - 1 - i; j++) {
                if(edges[j].weight > edges[j+1].weight) {
                    Edge tmp = edges[j];
                    edges[j] = edges[j+1];
                    edges[j+1] = tmp;
                }
            }
        }
    }

    /** 查找顶点返回对应下标*/
    private int getPosition(char ch) {
        for(int i = 0; i < vertexes.length; i++) {
            if(vertexes[i] == ch) {
                return i;
            }
        }
        return -1;
    }

    /** 获取邻接矩阵中的所有有效边*/
    private Edge[] getEdges() {
        int index = 0;
        Edge[] edges = new Edge[edgeCount];
        for(int i = 0; i < vertexes.length; i++) {
            for(int j = i+1; j <vertexes.length; j++) {
                if(matrix[i][j] != INF) {
                    edges[index++] = new Edge(vertexes[i], vertexes[j], matrix[i][j]);
                }
            }
        }
        return edges;
    }

    /** 获取下标为 i的顶点的终点, 用于判断后面两个顶点的终点是否相同
     * @param ends: 此参记录了各个顶点对应的终点, ends是在遍历过程中, 逐步形成的
     * @param i: 表示传入的顶点对应的下标
     *  @return 返回下标 i顶点对应的终点的下标*/
    private int getEnd(int[] ends, int i) { // i = 4 [0,0,0,0,5,0,0,0,0,0,0,0]
        while(ends[i] != 0) { /** 非等于0, 意思为 i(顶点下标)有对应的终点的下标*/
            i = ends[i];
        }
        return i;
    }

    /** 求出最小生成树*/
    public void kruskal() {
        /** 邻接矩阵中的所有有效边*/
        Edge[] edges = getEdges();
        System.out.println("邻接矩阵中的所有有效边: " + Arrays.toString(edges) + " 共"+ edges.length);
        /** 将边从小到大排序*/
        sortEdges(edges);
        /** 最终结果最小生成树*/
        Edge[] result = new Edge[edgeCount];
        /** 最终结果最小生成树的索引*/
        int index = 0;
        /** 保存`已有最小生成树`的每个顶点在最小生成树中的终点*/
        int[] ends = new int[edgeCount];
        /** 遍历邻接矩阵中的所有有效边*/
        for(int i = 0; i < edgeCount; i++) {
            /** 获取第 i条边的第1个顶点下标*/
            int p1 = getPosition(edges[i].start); // p1=4
            /** 获取第 i条边的第2个顶点下标*/
            int p2 = getPosition(edges[i].end); // p2=5
            /** 获取 p1顶点下标在已有最小生成树中的终点*/
            int m = getEnd(ends, p1); // m=4
            /** 获取 p2顶点下标在已有最小生成树中的终点*/
            int n = getEnd(ends, p2); // n=5
            /** 判断是否构成回路*/
            if(m != n) { /** 没有构成回路*/
                /** m(p1的终点下标)设置为`已有最小生成树 ends`的下标, 再将 n(p2的终点下标) 作为对应值保存<E,F> [0,0,0,0,5,0,0,0,0,0,0,0]*/
                ends[m] = n;
                /** 将第 i条有效边加到结果数组中*/
                result[index++] = edges[i];
            }
        }

        System.out.println("最小生成树为:");
        for(int i = 0; i < index; i++) {
            System.out.println(result[i]);
        }
    }
}

输出:
邻接矩阵为:
     0    12  9999  9999  9999    16    14
    12     0    10  9999  9999     7  9999
  9999    10     0     3     5     6  9999
  9999  9999     3     0     4  9999  9999
  9999  9999     5     4     0     2     8
    16     7     6  9999     2     0     9
    14  9999  9999  9999     8     9     0
邻接矩阵中的所有有效边: [Edge [<A,B>=12], Edge [<A,F>=16], Edge [<A,G>=14], Edge [<B,C>=10], Edge [<B,F>=7], Edge [<C,D>=3], Edge [<C,E>=5], Edge [<C,F>=6], Edge [<D,E>=4], Edge [<E,F>=2], Edge [<E,G>=8], Edge [<F,G>=9]] 共12
最小生成树为:
Edge [<E,F>=2]
Edge [<C,D>=3]
Edge [<D,E>=4]
Edge [<B,F>=7]
Edge [<E,G>=8]
Edge [<A,B>=12]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192

如果您觉得有帮助，欢迎点赞哦 ~ 谢谢!!