首页 > 代码库 > C++,Kruskal
C++,Kruskal
第一篇博客。
克鲁斯卡尔求最小生成树思想:首先将n个点看做n个独立的集合,将所有边快排(从小到大)。然后,按排好的顺序枚举每一条边,判断这条边连接的两个点是否属于一个集合。若是,则将这条边加入最小生成树,并将两个点所在的集合合并为一个集合。若否,则跳过。直到找到n-1条边为止。
#include<iostream> #include<algorithm> using namespace std; struct point{ int x; int y; int v; }; //写结构体用来构造边 point a[10000];//存边 int cmp(const point &a,const point &b){ if(a.v<b.v) return 1; else return 0; }//快排要用到的比较函数 ,从小到大 int fat[101]; int father(int x){ if(fat[x]!=x) return fat[x]=father(fat[x]); else return fat[x]; }//找出一个点属于哪个集合(找这个点的爹) void unionn(int x,int y){ int fa=father(x); int fb=father(y); if(fa!=fb) fat[fa]=fb; }//将被边连接的两个独立集合合并 int main(){ int i,j,n,m,k=0,ans=0,cnt=0; cin>>n; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { cin>>m; if(m!=0){ k++; a[k].x=i; a[k].y=j; a[k].v=m; } }//输入,存边 sort(a+1,a+1+k,cmp);//快排所有边 for(i=1;i<=n;i++){ fat[i]=i; }//初始化,将每个点看做独立集合 for(i=1;i<=k;i++){ if(father(a[i].x)!=father(a[i].y)){//如果这条边连接的两个点属于不同集合 ans+=a[i].v;//将这条边加入最小生成树 unionn(a[i].x,a[i].y);//将两个点所在的集合合并为一个集合 cnt++;//计数已添加的边 } if(cnt==n-1) break;//当已经有n-1条边的时候,结束 } cout<<ans; return 0; }
C++,Kruskal
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。