克鲁斯卡尔算法

应用场景-公交站问题

某城市新增7个站点(A, B, C, D, E, F, G) ,现在需要修路把7个站点连通

各个站点的距离用边线表示(权) ,比如 A – B 距离 12公里

问:如何修路保证各个站点都能连通,并且总的修建公路总里程最短?

克鲁斯卡尔算法基本介绍

克鲁斯卡尔(Kruskal)算法,是用来求加权连通图的最小生成树的算法。

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

具体做法:首先构造一个只含n个顶点的森林,然后依权值从小到大从连通网中选择边加入到森林中,并使森林中不产生回路,直至森林变成一棵树为止。


图解思路如下:

此时,最小生成树构造完成!它包括的边依次是:<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>

Kruskal算法重点需要解决的两个问题

问题一 :对图的所有边按照权值大小进行排序。
问题二 :将边添加到最小生成树中时,怎么样判断是否形成了回路。

问题一,很好解决,采用排序算法进行排序即可。

问题二,处理方式是:记录顶点在”最小生成树”中的终点,顶点的终点是”在最小生成树中与它连通的最大顶点”。然后每次需要将一条边添加到最小生存树时,判断该边的两个顶点的终点是否重合,重合的话则会构成回路。

在将<E,F> <C,D> <D,E>加入到最小生成树R中之后,这几条边的顶点就都有了终点:

(01) C的终点是F。
(02) D的终点是F。
(03) E的终点是F。
(04) F的终点是F。

关于终点的说明: 就是将所有顶点按照从小到大的顺序排列好之后;某个顶点的终点就是”与它连通的最大顶点”。

因此,接下来,虽然<C,E>是权值最小的边。但是C和E的终点都是F,即它们的终点相同,因此,将<C,E>加入最小生成树的话,会形成回路。这就是判断回路的方式。

这个终点的概念不太好理解,我看完韩顺平老师视频的代码后有点懵,这里应该引入个概念:并查集,所以学习代码前先学习并查集,于是找了篇博客和视频帮助了解。

CSDN:并查集详解(超级简单有趣~~就学会了)

B站:【算法】并查集(Disjoint Set)[共3讲]

公交站问题的代码实现

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
package com.nanzx.kruskal;

import java.util.ArrayList;
import java.util.Collections;

public class KruskalCase {

private EData[] edges; // 图中的边
private int edgeNum; // 边的个数
private char[] vertexs; // 顶点数组
private int[][] matrix; // 邻接矩阵
// 使用 INF 表示两个顶点不能连通
private static final int INF = Integer.MAX_VALUE;

public static void main(String[] args) {
char[] vertexs = { '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}};

KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);
kruskalCase.kruskal();
}

// 构造器
public KruskalCase(char[] vertexs, int[][] matrix) {
this.vertexs = vertexs;
this.matrix = matrix;
for (int i = 0; i < vertexs.length; i++) {
for (int j = i + 1; j < vertexs.length; j++) {
if (this.matrix[i][j] != INF) {
edgeNum++;
}
}
}
int index = 0;
edges = new EData[edgeNum];
for (int i = 0; i < vertexs.length; i++) {
for (int j = i + 1; j < vertexs.length; j++) {
if (this.matrix[i][j] != INF) {
edges[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]);
}
}
}
}

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

// 功能: 获取下标为i的顶点的终点,用于后面判断两个顶点的终点是否相同
private int getEnd(int[] parent, int i) {
while (parent[i] != 0) {
i = parent[i];
}
return i;
}

private void kruskal() {
//用于保存"已有最小生成树" 中的每个顶点在最小生成树中的终点
int[] parent = new int[vertexs.length];

//按照边的权值大小进行排序(从小到大)
ArrayList<EData> edgesList = new ArrayList<EData>();
Collections.addAll(edgesList, edges);
Collections.sort(edgesList);
System.out.println(edgesList);

// 创建结果数组, 保存最后的最小生成树
int index = 0;
EData[] rets = new EData[edgeNum];

for (int i = 0; i < edges.length; i++) {
int p1 = getPosition(edgesList.get(i).start);
int p2 = getPosition(edgesList.get(i).end);
int m = getEnd(parent, p1);
int n = getEnd(parent, p2);
if (m != n) {
parent[m]=n;
rets[index++] = edgesList.get(i);
}
}
// <E,F> <C,D> <D,E> <B,F> <E,G> <A,B>。
// 统计并打印 "最小生成树", 输出 rets
System.out.println("最小生成树为");
for (int i = 0; i < index; i++) {
System.out.println(rets[i]);
}
}
}

//创建一个类EData ,它的对象实例就表示一条边
class EData implements Comparable<EData> {
char start; // 边的一个点
char end; // 边的另外一个点
int weight; // 边的权值

public EData(char start, char 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;
}
}

运行结果:

[EData [<E, F>= 2], EData [<C, D>= 3], EData [<D, E>= 4], EData [<C, E>= 5], EData [<C, F>= 6], EData [<B, F>= 7], EData [<E, G>= 8], EData [<F, G>= 9], EData [<B, C>= 10], EData [<A, B>= 12], EData [<A, G>= 14], EData [<A, F>= 16]]
最小生成树为
EData [<E, F>= 2]
EData [<C, D>= 3]
EData [<D, E>= 4]
EData [<B, F>= 7]
EData [<E, G>= 8]
EData [<A, B>= 12]