【数据结构与算法】克鲁斯卡尔算法的介绍和公交站问题程序实现

1. 克鲁斯卡尔算法的介绍

和前面普里姆算法的介绍和修路问题程序实现的修路问题一样。克鲁斯卡尔(Kruskal)算法，也是用来求完全图的最小生成树的算法

基本思想：按照权重值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路

具体做法：先将各条边按权重值从小到大进行排序。从最小权重值的边开始，依次将各个边添加到生成树中。如果一条边添加到树中使树变成回路，则放弃该边的添加

2. 克鲁斯卡尔算法的原理

我们以公交站问题来说明克鲁斯卡尔算法的原理。用数组minTreeEdges保存最小生成树结果

首先将所有边按权重值从小到大进行排序，然后执行如下步骤：

1. 第1步：边的权重值最小，因此将边加入到最小生成树minTreeEdges中
2. 第2步：上一步操作之后，边的权重值最小，因此将边加入到最小生成树minTreeEdges中
3. 第3步：上一步操作之后，边的权重值最小，因此将边加入到最小生成树minTreeEdges中
4. 第4步：上一步操作之后，边的权重值最小，但会和已有的子树构成回路；因此跳过边。同理跳过边。将边加入到最小生成树minTreeEdges中
5. 第5步：上一步操作之后，边的权重值最小，因此将边加入到最小生成树minTreeEdges中
6. 第6步：上一步操作之后，边的权重值最小，但会和已有的子树构成回路；因此跳过边。同理跳过边。将边加入到最小生成树minTreeEdges中

此时最小生成树构造完成。它包括的边依次是：、、、、、

2.1 将边添加到已有生成树之前，判断是否形成了回路

生成树的终点：就是将所有顶点按照从小到大的顺序排列之后；某个顶点的终点就是该顶点在已有生成树的最大顶点

基本原理：一条边较小的顶点为起点，较大的顶点为终点。得到起点所在已有生成树的最大字符的顶点V1，得到终点所在已有生成树的最大字符的顶点V2，如果V1和V2相等，则表示起点和终点已经在同一颗生成树中，如果将起点和终点连通，则会形成回路。如果V1和V2不相等，则表示起点和终点在不同的生成树中，可以将该边添加到已有生成树中

示例说明：

如上所示：将、、加入到最小生成树minTreeEdges中之后，这颗生成树的终点都是F

因此，接下来虽然是权值最小的边。但是C和E的终点都是F，即它们的终点相同，因此会形成回路

3. 公交站问题的介绍

和前面普里姆算法的介绍和修路问题程序实现的修路问题一样，我们来看一个公交站问题，如下所示：

问题：有7个公交站A、B、C、D、E、F、G，各个公交站之间的距离(权)用边线表示，比如A -> B距离12公里。如何让各个公交站都能连通，并且总的修路里程最短

程序如下：

import java.util.Arrays;

public class KruskalCase {

    // 边的个数
    private int edgeNum;
    // 顶点集合
    private char[] vertexs;
    // N个顶点形成的N * N二维数组，用来保存顶点之间的距离
    private int[][] weights;

    // 用INFINITY表示距离无限大，不能连通
    private static final int INFINITY = Integer.MAX_VALUE;

    public static void main(String[] args) {
        char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};

        // N个顶点形成的N * N二维数组，用来保存顶点之间的距离
        // 用INFINITY表示距离无限大，不能连通
        int[][] weights = {
                {0, 12, INFINITY, INFINITY, INFINITY, 16, 14},
                {12, 0, 10, INFINITY, INFINITY, 7, INFINITY},
                {INFINITY, 10, 0, 3, 5, 6, INFINITY},
                {INFINITY, INFINITY, 3, 0, 4, INFINITY, INFINITY},
                {INFINITY, INFINITY, 5, 4, 0, 2, 8},
                {16, 7, 6, INFINITY, 2, 0, 9},
                {14, INFINITY, INFINITY, INFINITY, 8, 9, 0}
        };

        // 创建KruskalCase对象
        KruskalCase kruskalCase = new KruskalCase(vertexs, weights);

        // 输出weights
        kruskalCase.show();

        // 测试克鲁斯卡尔算法
        kruskalCase.kruskal();
    }

    // 构造器
    public KruskalCase(char[] vertexs, int[][] weights) {
        // 顶点数
        int vertexNum = vertexs.length;

        // 初始化顶点, 并进行赋值
        this.vertexs = new char[vertexNum];
        for (int i = 0; i < vertexs.length; i++) {
            this.vertexs[i] = vertexs[i];
        }

        // 初始化二维数组，并进行赋值
        this.weights = new int[vertexNum][vertexNum];
        for (int i = 0; i < vertexNum; i++) {
            for (int j = 0; j < vertexNum; j++) {
                this.weights[i][j] = weights[i][j];
            }
        }

        // 统计边的条数
        for (int i = 0; i < vertexNum; i++) {
            // 只统计右上三角的
            for (int j = i + 1; j < vertexNum; j++) {
                if (this.weights[i][j] != INFINITY) {
                    edgeNum++;
                }
            }
        }
    }

    // 显示二维数组，即显示顶点之间的距离
    public void show() {
        System.out.println("二维数组为: ");
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = 0; j < vertexs.length; j++) {
                System.out.printf("%12d", weights[i][j]);
            }
            System.out.println();
        }
    }

    // 从weights二维数组中，形成Edge数组
    private Edge[] getEdges() {
        Edge[] edges = new Edge[edgeNum];
        // edges的index从0开始
        int edgeIndex = 0;

        for (int i = 0; i < vertexs.length; i++) {
            // 只处理右上三角的
            for (int j = i + 1; j < vertexs.length; j++) {
                if (weights[i][j] != INFINITY) {
                    // 因为处理的是右上三角的，所以i比j小，正好对应起点和终点
                    edges[edgeIndex++] = new Edge(vertexs[i], vertexs[j], weights[i][j]);
                }
            }
        }
        return edges;
    }

    // 使用冒泡排序算法，对edges中的边，按权重值由小到大排列
    private void sortEdges(Edge[] edges) {
        Edge tmpEdge = null;

        // 用于控制遍历多少轮
        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) {//交换
                    tmpEdge = edges[j];
                    edges[j] = edges[j + 1];
                    edges[j + 1] = tmpEdge;
                }
            }
        }
    }

    // 根据顶点的值，返回顶点的index。查找不到则返回-1
    private int getVertexIndex(char vertex) {
        for (int i = 0; i < vertexs.length; i++) {
            if (vertexs[i] == vertex) {
                return i;
            }
        }

        // 找不到, 则返回-1
        return -1;
    }

    // 从vertexEndIndexs找到index为vertexIndex的顶点的终点的index
    private int getVertexEndIndex(int[] vertexEndIndexs, int vertexIndex) {
        // 如果找不到终点，则直接返回该顶点的index
        // 如果找到了终点。可能该终点还有终点，迭代处理。返回最终的终点的index
        while (vertexEndIndexs[vertexIndex] != 0) {
            vertexIndex = vertexEndIndexs[vertexIndex];
        }
        return vertexIndex;
    }

    // 克鲁斯卡尔算法实现
    public void kruskal() {
        // 保存每个顶点在最小生成树的终点的index，这是一个动态的过程
        int[] vertexEndIndexs = new int[vertexs.length];
        // 保存最小生成树的所有边
        Edge[] minTreeEdges = new Edge[vertexs.length - 1];
        int minTreeEdgeIndex = 0;

        // 获取图中所有的边的集合
        Edge[] edges = getEdges();
        System.out.println("图共" + edges.length + "条边，图的边的集合 = " + Arrays.toString(edges));

        // 对edges中的边，按权重值由小到大排列
        sortEdges(edges);

        // 遍历edges数组，将边添加到最小生成树中时。如果没有形成回路，就添加到minTreeEdges, 否则不添加
        for (int i = 0; i < edgeNum; i++) {
            // 获取第i条边的顶点(起点)的index
            int startVertexIndex = getVertexIndex(edges[i].startVertex);
            // 获取第i条边的顶点(终点)的index
            int endVertexIndex = getVertexIndex(edges[i].endVertex);

            // 获取边的顶点(起点)在当前最小生成树的终点index
            int startVertexEndIndex = getVertexEndIndex(vertexEndIndexs, startVertexIndex);
            // 获取边的顶点(终点)在当前最小生成树的终点index
            int endVertexEndIndex = getVertexEndIndex(vertexEndIndexs, endVertexIndex);

            // 如果不构成回路
            if (startVertexEndIndex != endVertexEndIndex) {
                // startVertexEndIndex是一条边的起点所在已有子树A的终点index
                // endVertexEndIndex是该边的终点所在已有子树B的终点index
                // 赋值之前vertexEndIndexs[startVertexEndIndex]的值肯定是0，且startVertexEndIndex小于endVertexEndIndex
                // vertexEndIndexs[startVertexEndIndex] = endVertexEndIndex相当于给子树A设置新的终点index
                vertexEndIndexs[startVertexEndIndex] = endVertexEndIndex;

                // 将符合条件的边，添加到minTreeEdges
                minTreeEdges[minTreeEdgeIndex++] = edges[i];
            }
        }

        // 输出各个顶点的终点index数组
        System.out.println("各个顶点的终点index：" + Arrays.toString(vertexEndIndexs));

        // 输出最小生成树
        System.out.println("最小生成树为：");
        for (int i = 0; i < minTreeEdgeIndex; i++) {
            System.out.println(minTreeEdges[i]);
        }

    }

}

// 用来表示一条边
class Edge {
    // 边的一个顶点(起点)
    char startVertex;
    // 边的一个顶点(终点)
    char endVertex;
    // 边的权重值
    int weight;

    public Edge(char startVertex, char endVertex, int weight) {
        this.startVertex = startVertex;
        this.endVertex = endVertex;
        this.weight = weight;
    }

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

}
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
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211

运行程序，结果如下：

二维数组为: 
           0          12  2147483647  2147483647  2147483647          16          14
          12           0          10  2147483647  2147483647           7  2147483647
  2147483647          10           0           3           5           6  2147483647
  2147483647  2147483647           3           0           4  2147483647  2147483647
  2147483647  2147483647           5           4           0           2           8
          16           7           6  2147483647           2           0           9
          14  2147483647  2147483647  2147483647           8           9           0
图共12条边，图的边的集合 = [Edge [ = 12], Edge [ = 16], Edge [ = 14], Edge [ = 10], Edge [ = 7], Edge [ = 3], Edge [ = 5], Edge [ = 6], Edge [ = 4], Edge [ = 2], Edge [ = 8], Edge [ = 9]]
各个顶点的终点index：[6, 5, 3, 5, 5, 6, 0]
最小生成树为：
Edge [ = 2]
Edge [ = 3]
Edge [ = 4]
Edge [ = 7]
Edge [ = 8]
Edge [ = 12]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17