Kruskal算法

发布 : 2020-06-20 分类 : 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
*/
本文作者 : preccrep
原文链接 : https://preccrep.github.io/2020/06/20/Kruskal%E7%AE%97%E6%B3%95/
版权声明 : 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
留下足迹

博客已萌萌哒运行(●'◡'●)ノ♥
Theme - BMW | Made With 💗 | Powered by GodBMW