kruskal法是一种贪心算法,与prim算法相似。

在kruskal算法中,我们用到了并查集。

算法的思想是这样的:

  1. 对所有的顶点建立一个并查集,对所有的边先进行排序
  2. 遍历每一条边,(因为我们之前对边进行排过序,所以我们每次都是选择最短的边),如果边的两个端点不在通一个集合里,那么该边属于最小生成树,将该边记录下来,然后将两个端点所在的集合合并
  3. 最后我们就得到了最小生成树的所有的边,因为我们每次都是选取可以选取的最小的边,所以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
104
105
106
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
struct edge {
int from, to;
int val;
edge(int from, int to, int val):from(from), to(to), val(val){}
};
const int MAX_V = 5000; //最大边数
int V; //边数
vector<edge> edges; //边
//并查集
int par[MAX_V]; //节点的父节点
int height[MAX_V]; //树的高度
//初始化并查集
void init(int n) {
for (int i = 0; i < n; i++) {
par[i] = i;
height[i] = 0;
}
}
//找出x所在树的根节点
int find(int x) {
if (par[x] == x) {
return x;
} else {
return par[x] = find(par[x]); //把父节点直接指向根节点
}
}
//合并x,y所属的集合
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y)
return;
//如果x所在集合树的高度小于y所在集合树的高度,那么将
//x的父节点指向y,反之亦然
//如果x,y所在集合的树的高度相等,那么随便怎么样都行,
//但是将最后指向的树的高度加一
if (height[x] < height[y]) {
par[x] = y;
} else {
par[y] = x;
if (height[x] == height[y])
height[x]++;
}
}
bool mycompare(edge e1, edge e2) {
return e1.val < e2.val;
}
void kruskal() {
sort(edges.begin(), edges.end(), mycompare); //排序
for (int i = 0; i < edges.size(); i++) {
cout<<edges[i].val<<endl;
}
init(V); //初始化并查集
vector<edge> result;
for (int i = 0; i < edges.size(); i++) {
if (find(edges[i].from) != find(edges[i].to)) {
result.push_back(edges[i]);
unite(edges[i].from, edges[i].to);
}
}
for (int i = 0; i < result.size(); i++) {
cout<<result[i].from << '\t' << result[i].to<<endl;
}
}
int main() {
/* example input
4
0 9 6 4
9 0 7 x
6 7 0 4
4 x 4 0
*/
cin>>V;
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
char w;
cin>>w;
if (i < j && w != 'x') { //支取上三角
edge e(i, j, w - '0');
edges.push_back(e);
}
}
}
kruskal();
}