Kruskal算法

Kruskal算法是基于贪心的思想得到的。首先我们把所有的边按照权值从小到大排列,接着按照顺序选取每条边,如果这条边的两个端点不属于同一集合,那么就将它们合并,直到所有的点都属于同一个集合为止。至于怎么合并到一个集合,那么这里我们就可以用到一个工具:并查集。实际上,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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct node{
int head, tail;
int len;
};

bool cmp(const node& a, const node& b){
return a.len < b.len;
}

void kruskal(vector<node> &arr, vector<bool> &visited){
for(int i = 0; i < arr.size(); i++)
cin >> arr[i].head >> arr[i].tail >> arr[i].len;
sort(arr.begin(), arr.end(), cmp);
for(int i = 0; i < visited.size(); i++)
visited[i] = false;
int ans = 0;
for(int i = 0; i < arr.size(); i++){
if((!visited[arr[i].head]) || (!visited[arr[i].tail])){
visited[arr[i].head] = visited[arr[i].tail] = true;
ans += arr[i].len;
cout << arr[i].head << "-->" << arr[i].tail << ": " << arr[i].len << endl;
}
}
cout << ans << endl;
}

int main(){
int N, M; //N is the number of edges, M is the number of nodes
cin >> N >> M;
vector<node> arr(N);
vector<bool> visited(M);
kruskal(arr, visited);
return 0;
}
/*
Input:
8 6
0 1 2
0 2 1
1 3 5
2 3 4
1 2 3
2 4 1
4 5 2
3 5 3
Output:
0-->2: 1
2-->4: 1
0-->1: 2
4-->5: 2
3-->5: 3
9
*/