数据结构与算法——图(二)

前几天学习完图的遍历后,马上就开始了图的最小生成树,结果就心态爆炸,完全理解不了这两个算法——prim算法与Kruskal算法。接下来将对这两个算法进行解密,并且提供简单易于理解的解释。

Prim算法

首先熟悉一下接下来需要求最小生成树的图:

图

如果还不了解图的话,还是建议先理解数据结构与算法——图(一)的内容。接下来的内容会让大脑感到非常舒适,请坚持住!

作为一名程序员我们还是先看看代码吧,只需要关注prim方法即可。

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
public class GraphPrim<T> {

public static void main(String[] args) {
Integer[] vertex = new Integer[] { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
int[][] matrix = new int[][] {
{ 0, 10, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT },
{ 10, 0, 18, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, MAX_WEIGHT, 12 },
{ MAX_WEIGHT, 18, 0, 22, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 8 },
{ MAX_WEIGHT, MAX_WEIGHT, 22, 0, 20, MAX_WEIGHT, 24, 16, 21 },
{ MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 20, 0, 26, MAX_WEIGHT, 7, MAX_WEIGHT },
{ 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 26, 0, 17, MAX_WEIGHT, MAX_WEIGHT },
{ MAX_WEIGHT, 16, MAX_WEIGHT, 24, MAX_WEIGHT, 17, 0, 19, MAX_WEIGHT },
{ MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, 7, MAX_WEIGHT, 19, 0, MAX_WEIGHT },
{ MAX_WEIGHT, 12, 8, 21, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 0 },
};
GraphPrim<Integer> graph = new GraphPrim<>(vertex, matrix);
graph.prim();
}

public static final int MAX_WEIGHT = 100000;
private T[] vertex;
private int[][] matrix;

public GraphPrim(T[] vertex, int[][] matrix) {
this.vertex = vertex;
this.matrix = matrix;
}

public void prim() {
int size = this.vertex.length;
int[] cost = new int[size];
int[] index = new int[size];
int min, minIndex, sum = 0;
for (int i = 0; i < size; i++) {
cost[i] = this.matrix[0][i];
}
for (int i = 1; i < size; i++) {
min = MAX_WEIGHT;
minIndex = 0;
for (int j = 1; j < size; j++) {
if (cost[j] > 0 && cost[j] < min) {
min = cost[j];
minIndex = j;
}
}
System.out.println("顶点: " + this.vertex[minIndex] + " 权值: " + min);
sum += min;
cost[minIndex] = 0;
index[minIndex] = min;
for (int j = 1; j < size; j++) {
if (cost[j] != 0 && this.matrix[minIndex][j] < cost[j]) {
cost[j] = this.matrix[minIndex][j];
}
}
}
System.out.println(sum + " 最小生成树数组: " + Arrays.toString(index));
}
}

根据上图,这样的解出来的结果是( 99 最小生成树权值总和数组: [0, 10, 8, 16, 7, 11, 16, 19, 12] )。为什么会是这样的结果呢?我们将这个过程当做修路来思考,每条边的权值就是修路的花费。

  • 从顶点0开始,当我们在顶点0时,我们只能看到顶点1与顶点5的距离,那么我们会选择以修顶点0到顶点1的路。
  • 当修到顶点1时,我们能看到顶点2、顶点8、顶点6与顶点5,那么这时候顶点5的花费是最小的,我们就修了顶点0到顶点5的路。
  • 这时候又多了几个选择,我们以箭头表示(v1->v2, v1->v8, v1->v6, v5->v6, v5->v4),再根据之前的做法,选择花费最小的路,依次循环下去,直到每个地方都去过为止。

这就是prim算法的思路,图解如下:

图解prim过程
图解prim过程

Kruskal算法

实际上Kruskal算法也差不多,只不过它更简单一些,思路非常简单,那就是根据邻接表按权值排序从小到大找非回环路线。下面用一张图来表示它的执行过程:

Kruskal算法图示
Kruskal算法图示

这里对上图进行解释一下,图上邻接表中表示的1-15是循环的轮次,图中的箭头为对应轮次不造成回环响应的轮次。

  • 第一次从邻接表的第一个开始,即顶点4顶点7然后发现没有回环,进行将其走势存到parent数组中,进行下一轮循环。
  • 第二次从邻接表的第二个开始,即顶点2顶点8然后发现没有回环,继续下去,并且走到第七轮都没有发现回环。
  • 第八轮从邻接表的第八个开始时,发现从顶点5顶点6的话会出现回环,因此不进行任何操作,剩下的节点除了第十轮外,都因为产生了回环,所以最终结果就是sum为99。

其最终的parent数组的情况为{1,5,8,7,7,8,7,0,6,0,0,0,0,0,0}。下面附上Kruskal算法的代码:

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
package graph;

import com.sun.javafx.geom.Edge;

import java.util.Arrays;

/**
* 克鲁斯卡尔算法
*/
public class GraphKruskal<T> {

public static void main(String[] args) {
Integer[] vertex = new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
Edge[] table = new Edge[15];
table[0] = new Edge(4, 7, 7);
table[1] = new Edge(2, 8, 8);
table[2] = new Edge(0, 1, 10);
table[3] = new Edge(0, 5, 11);
table[4] = new Edge(1, 8, 12);
table[5] = new Edge(3, 7, 16);
table[6] = new Edge(1, 6, 16);
table[7] = new Edge(5, 6, 17);
table[8] = new Edge(1, 2, 18);
table[9] = new Edge(6, 7, 19);
table[10] = new Edge(3, 4, 20);
table[11] = new Edge(3, 8, 21);
table[12] = new Edge(2, 3, 22);
table[13] = new Edge(3, 6, 24);
table[14] = new Edge(4, 5, 26);
GraphKruskal<Integer> graphs = new GraphKruskal<>(vertex, table);
graphs.kruskal();
}

private T[] vertex;
private Edge[] table;

public GraphKruskal(T[] vertex, Edge[] table) {
this.vertex = vertex;
this.table = table;
}

public void kruskal() {
int begin, end, sum = 0;
int[] parent = new int[table.length];
for (int i = 0; i < table.length; i++) {
parent[i] = 0;
}
for (int i = 0; i < table.length; i++) {
begin = find(parent, table[i].getBeginIndex());
end = find(parent, table[i].getEndIndex());
if (begin != end) {
parent[begin] = end;
System.out.println(begin + " -> " + end);
sum += table[i].getWeight();
}
}
System.out.println("sum = " + sum);
}

private int find(int[] parent, int index) {
while (parent[index] > 0) {
index = parent[index];
}
return index;
}

private static class Edge {
private int beginIndex;
private int endIndex;
private int weight;

public Edge(int beginIndex, int endIndex, int weight) {
this.beginIndex = beginIndex;
this.endIndex = endIndex;
this.weight = weight;
}

public int getBeginIndex() {
return beginIndex;
}

public void setBeginIndex(int beginIndex) {
this.beginIndex = beginIndex;
}

public int getEndIndex() {
return endIndex;
}

public void setEndIndex(int endIndex) {
this.endIndex = endIndex;
}

public int getWeight() {
return weight;
}

public void setWeight(int weight) {
this.weight = weight;
}
}

}

现在算是初步理解了Prim算法和Kruskal算法的基本原理了,文中有表述不到位或者表述不当的地方,可以联系我,大家一起共同学习共同进步!