释放双眼，带上耳机，听听看~！
最小生成树
在含有n个顶点的连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。
example：
例如，对于如上图G4所示的连通网可以有多棵权值总和不相同的生成树。
克鲁斯卡尔(Kruskal)算法
克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法，基于连续的按照最小边的策略进行生成树的构建。Kruskal算法开始的时候把每个顶点都当做棵树，这样就是个森林，然后选取最小的边进行树的连接，最后生成只含有一棵树。
基本思想：将图的存储结构使用边集数组的形式表示，并将边集数组按权值从小到大排序，遍历边集数组，每次选取一条边并判断是否构成环路，不会构成环路则将其加入最小生成树，最终只会包含n-1条边(n为无向图的顶点数)。
具体做法：
- 每次选取最小的边来构成生成树
- 将这条边加入后不能形成闭环
伪代码：
图解：
第1步：将边<E,F>加入R中。
边<E,F>的权值最小，因此将它加入到最小生成树结果R中。
第2步：将边<C,D>加入R中。
上一步操作之后，边<C,D>的权值最小，因此将它加入到最小生成树结果R中。
第3步：将边<D,E>加入R中。
上一步操作之后，边<D,E>的权值最小，因此将它加入到最小生成树结果R中。
第4步：将边<B,F>加入R中。
上一步操作之后，边<C,E>的权值最小，但<C,E>会和已有的边构成回路；因此，跳过边<C,E>。同理，跳过边<C,F>。将边<B,F>加入到最小生成树结果R中。
第5步：将边<E,G>加入R中。
上一步操作之后，边<E,G>的权值最小，因此将它加入到最小生成树结果R中。
第6步：将边<A,B>加入R中。
上一步操作之后，边<F,G>的权值最小，但<F,G>会和已有的边构成回路；因此，跳过边<F,G>。同理，跳过边<B,C>。将边<A,B>加入到最小生成树结果R中。
此时，最小生成树构造完成！它包括的边依次是：<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>。
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
2
3import java.util.ArrayList;
4import java.util.List;
5
6public class Kruskal {
7
8 /** 邻接矩阵, 为二维数组, 也称地图 */
9 private int[][] matrix;
10 /** 设置最大权重范围, 表示正无穷 */
11 private int MAX_WEIGHT = Integer.MAX_VALUE;
12 /** 边集数组, 采用List接口的实现类ArrayList（数组线性表）, 遍历元素和随机访问元素的效率比较高 */
13 private List<Edge> edgeList = new ArrayList<Edge>();
14
15 /**
16 * 创建地图
17 */
18 private void createGraph(int index) { //index表示顶点个数
19 matrix = new int[index][index]; //邻接矩阵是一个长宽相等的正方形矩阵
20 //邻接矩阵中每一行的数组, 按照原图以此填充
21 int[] v0 = { 0, 10, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT };
22 int[] v1 = { 10, 0, 18, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, MAX_WEIGHT, 12 };
23 int[] v2 = { MAX_WEIGHT, 18, 0, 22, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 8 };
24 int[] v3 = { MAX_WEIGHT, MAX_WEIGHT, 22, 0, 20, MAX_WEIGHT, MAX_WEIGHT, 16, 21 };
25 int[] v4 = { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 20, 0, 26, MAX_WEIGHT, 7, MAX_WEIGHT };
26 int[] v5 = { 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 26, 0, 17, MAX_WEIGHT, MAX_WEIGHT };
27 int[] v6 = { MAX_WEIGHT, 16, MAX_WEIGHT, 24, MAX_WEIGHT, 17, 0, 19, MAX_WEIGHT };
28 int[] v7 = { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, 7, MAX_WEIGHT, 19, 0, MAX_WEIGHT };
29 int[] v8 = { MAX_WEIGHT, 12, 8, 21, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 0 };
30 matrix[0] = v0;
31 matrix[1] = v1;
32 matrix[2] = v2;
33 matrix[3] = v3;
34 matrix[4] = v4;
35 matrix[5] = v5;
36 matrix[6] = v6;
37 matrix[7] = v7;
38 matrix[8] = v8;
39 }
40
41 /**
42 * 创建边集数组，并且对他们按权值从小到大排序（顺序存储结构也可以认为是数组吧）
43 */
44 public void createEdges() {
45 //调用带参构造，此处三个参数分别为begin,end,weight
46 Edge v0 = new Edge(4, 7, 7);
47 Edge v1 = new Edge(2, 8, 8);
48 Edge v2 = new Edge(0, 1, 10);
49 Edge v3 = new Edge(0, 5, 11);
50 Edge v4 = new Edge(1, 8, 12);
51 Edge v5 = new Edge(3, 7, 16);
52 Edge v6 = new Edge(1, 6, 16);
53 Edge v7 = new Edge(5, 6, 17);
54 Edge v8 = new Edge(1, 2, 18);
55 Edge v9 = new Edge(6, 7, 19);
56 Edge v10 = new Edge(3, 4, 20);
57 Edge v11 = new Edge(3, 8, 21);
58 Edge v12 = new Edge(2, 3, 22);
59 Edge v13 = new Edge(3, 6, 24);
60 Edge v14 = new Edge(4, 5, 26);
61
62 //同时加入边集数组中（数组线性表）
63 edgeList.add(v0);
64 edgeList.add(v1);
65 edgeList.add(v2);
66 edgeList.add(v3);
67 edgeList.add(v4);
68 edgeList.add(v5);
69 edgeList.add(v6);
70 edgeList.add(v7);
71 edgeList.add(v8);
72 edgeList.add(v9);
73 edgeList.add(v10);
74 edgeList.add(v11);
75 edgeList.add(v12);
76 edgeList.add(v13);
77 edgeList.add(v14);
78 }
79
80 /**
81 * 克鲁斯卡尔算法
82 */
83 public void kruskal() {
84 //创建图和边集数组, 该图有v0-v8共9个顶点s
85 createGraph(9);
86 //可以由图转出边集数组并按权从小到大排序，这里为了方便观察直接写出来了
87 createEdges();
88
89 //定义一个数组用来判断边与边是否形成环路（并查集知识）
90 int[] parent = new int[9];
91
92 /** 权值总和, 是判断最小生成树的重要依据 , 初始化为0 */
93 int sum = 0;
94
95 int n, m;
96
97 //遍历得到每一条边
98 for (int i = 0; i < edgeList.size(); i++) {
99 Edge edge= edgeList.get(i);
100 n = find(parent, edge.getBegin());
101 m = find(parent, edge.getEnd());
102
103 //如果 m == n 说明形成了环路或者两个结点都在一棵树上
104 //反之，如果 n和m 不等则说明没有闭合线路
105 if (n != m) {
106 parent[n] = m; // 设置n在"已有的最小生成树"中的终点为m（就是把n合并在m所在的连通分量中）
107 System.out.println("(" + edge.getBegin() + "," + edge.getEnd() + ")" +edge.getWeight());
108
109 sum += edge.getWeight(); //加上对应边的权重，更新sum值
110 }
111 }
112
113 System.out.println("权值总和为：" + sum);
114 }
115
116 public int find(int[] parent, int index) {
117 while (parent[index] > 0) {
118 //parent[0] = 1表示顶点0,1已经加入生成树中
119 index = parent[index];
120 }
121 return index;
122 }
123
124 public static void main(String[] args) {
125 Kruskal graph = new Kruskal();
126 graph.kruskal();
127 }
128
129}
130
131
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
2
3/**
4 * 克鲁斯卡尔->最小生成树边实体
5 * @author Administrator
6 *
7 */
8class Edge {
9
10 private int begin; //边的起点
11 private int end; //边的终点
12 private int weight; //边的权重
13
14 public Edge(int begin, int end, int weight) { //带参构造
15 super();
16 this.begin = begin;
17 this.end = end;
18 this.weight = weight;
19 }
20
21 public int getBegin() {
22 return begin;
23 }
24
25 public void setBegin(int begin) {
26 this.begin = begin;
27 }
28
29 public int getEnd() {
30 return end;
31 }
32
33 public void setEnd(int end) {
34 this.end = end;
35 }
36
37 public int getWeight() {
38 return weight;
39 }
40
41 public void setWeight(int weight) {
42 this.weight = weight;
43 }
44
45 @Override
46 public String toString() {
47 return "Edge [begin=" + begin + ", end=" + end + ", weight=" + weight + "]";
48 }
49
50}
51
52
代码中所用的图数据如下：
运行结果：
