图论学习 Kruskal算法求最小生成树
作者:
travel2.0
,
2024-01-27 11:00:31
,
所有人可见
,
阅读 60
Kruskal算法求最小生成树
算法分析:
1.因为只是单纯遍历每一条边,我们可以用struct存储;
(这样就算无向图也不用存两遍,也无需考虑自环,重边,因为权值都会遍历到)
3.将边从小到大排序;
4.因为集合问题,如果存在最小生成树的话,当遍历到一定程度之后所有点都在一个集合里面,后续的遍历没啥用;
5.res 存储权值,cnt 存储边数(cnt < n-1 的话不存在)
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N = 2e5+10;
struct Edge{
int a,b,w;
bool operator < (const Edge &x)const{
return w< x.w;
}
}edges[N];
int p[N];
int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main(){
cin>>n>>m;
for(int i = 1;i <= m;i++){
int a,b,c; cin>>a>>b>>c;
edges[i] = {a,b,c};
}
sort(edges + 1,edges + 1 + m);
for(int i = 1;i <= n;i++) p[i] = i;
int res = 0,cnt = 0;
for(int i = 1;i <= m;i++){
int a = edges[i].a,b = edges[i].b,w = edges[i].w;
if(find(a) != find(b)) { //一段时间后,后续的find(a) == find(b);
res +=w;
cnt++;
p[find(a)] = find(b);
}
}
if(cnt < n - 1) cout<<"impossible";
else cout<<res<<endl;
return 0;
}