c++最小生成树kruskal算法
时间: 2024-05-30 15:06:39 浏览: 19
C++中最小生成树Kruskal算法是一种基于贪心策略的算法,用于在加权连通图中查找最小生成树。以下是Kruskal算法的步骤:
1. 将所有边按照权值从小到大排序。
2. 从权值最小的边开始,逐个添加到生成树中,若添加该边后生成树不会形成环,则加入该边,否则舍弃该边。
3. 重复步骤2,直到生成树包含了图中的所有节点。
以下是C++代码示例:
```c++
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;//最大点数
const int maxm=20005;//最大边数
int fa[maxn];//并查集数组
struct edge{
int u,v,w;
}e[maxm];//存储边的信息,包括起点、终点、权值
bool cmp(edge a,edge b){
return a.w<b.w;//将边按照权值从小到大排序
}
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);//并查集查找
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) fa[i]=i;//初始化并查集
for(int i=1;i<=m;i++){
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
}
sort(e+1,e+m+1,cmp);//按照权值从小到大排序
int cnt=0,ans=0;
for(int i=1;i<=m;i++){
int x=find(e[i].u),y=find(e[i].v);
if(x!=y){//如果两个点不在同一个连通块中
fa[x]=y;
ans+=e[i].w;//加入该边
cnt++;
if(cnt==n-1) break;//如果加入的边数等于n-1,则退出循环
}
}
printf("%d",ans);
return 0;
}
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)