克鲁斯卡尔算法

应用场景-公交站问题

某城市新增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]