首页 技术 正文
技术 2022年11月23日
0 收藏 361 点赞 4,729 浏览 1215 个字

Kruskal算法就是把图中的所有边权值排序,然后从最小的边权值开始查找,连接图中的点,当该边的权值较小,但是连接在途中后会形成回路时就舍弃该边,寻找下一边,以此类推,假设有n个点,则只需要查找n-1条边即可。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn=;
int v,l;///v代表点的个数,l代表边的个数
int fa[maxn],son[maxn];
struct Kruskal{///该结构体时存储点与这两点之间的距离的
int a,b;
int value;
}edge[maxn];
bool cmp(Kruskal x,Kruskal y){///把边的权值按从小到大的顺序排列
return x.value<y.value;
}
int fin(int x)///寻找x的根结点
{
return fa[x]==x?fa[x]:fin(fa[x]);
}
bool unin(int x,int y)
{
int root1,root2;
root1=fin(x);
root2=fin(y);
if(root1==root2){
return false;///当输入的两个点有相同的根结点时成环,返回false
}
else if(son[root1]>=son[root2]){
fa[root2]=root1;///root2的根结点时root1
son[root1]+=son[root2];///把数量少的那棵树连接到数量多的那棵树
}
else {
fa[root1]=root2;
son[root2]+=son[root1];
}
return true;///只要两个点不在同一个根结点上就返回true
}
int main()
{
int n,total,sum,flag;
cin>>n;
while(n--){
cin>>v>>l;
total=;
sum=;
flag=;
for(int i=;i<=v;i++){///初始化
fa[i]=i;
son[i]=;
}
for(int i=;i<=l;i++){
cin>>edge[i].a>>edge[i].b>>edge[i].value; }
sort(edge+,edge++l,cmp);///因为edge时从1开始的,所以edge要+1
for(int i=;i<=l;i++){
if(unin(edge[i].a,edge[i].b)){
total++;
sum+=edge[i].value;///记录最小的权值
cout<<edge[i].a<<"->"<<edge[i].b<<endl;
}
if(total==v-){///有n个结点就有n-1条边构成最小生成树
flag=;
break;
} }
if(flag)cout<<sum<<endl;
else cout<<"data error ."<<endl; }
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141153.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:7,142
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:4,476
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:567 阅读:5,291
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:5,163
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:6,335
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,874