最小生成树（kruskal）

比眉伴天荒 2021-06-22 15:37 422阅读 0赞

**伪代码**

res 最小生成树中的权重之和
    cnt 当前加了多少条边
    将所有边按权重排序O(mlogm)
    枚举每条边（并查集应用） 
        if a,b 不连通
            加入集合

#include <iostream>
    #include <cstring>
    #include <algorithm> 
    using namespace std;
    const int maxn=2e5+10;
    const int INF=0x3f3f3f3f; 
    int n,m; 
    int f[maxn];//并查集的数组

struct edges{ 
    	int a,b,w;
    }edg[maxn];

bool cmp(edges p,edges q){ 
    	 return p.w<q.w;//按权重大小排序 
    }

int find(int x){ //返回的是当前节点的祖宗节点
    	if(x!=f[x]){ 
    		f[x]=find(f[x]);//并查集的路劲压缩 
    	}
    	return f[x];
    }

int Kruskal(){ 
    	int res=0,num=0;
    	  //res 最小生成树中的权重之和
          //num 当前加了多少条边 
        for(int i=0;i<m;i++){ //遍历所有边 
        	 int a=edg[i].a,b=edg[i].b;
        	 int a=find(a),b=find(b);//找到a和b的祖先 
        	 if(a!=b){ //如果a和b不在同一个集合 
        	 	 f[a]=b;//就将a和b合并 
        	 	 num++;//集合中边数加一 
        	 	 res+=edg[i].w; 
    		 }
    	}
    	if(num<n-1){ //如果加入的边数小于n-1个，说明不连通不存在最小生成树 
    		return INF;
    	}
       else{ 
       	return res;
       }
    }

int main(){ 
    	 cin>>n>>m;
    	 for(int i=1;i<=n;i++){ 
    	 	 f[i]=i;
    	 }
    	 for(int i=0;i<m;i++){ 
    	 	int a,b,c;
    	 	cin>>a>>b>>c;
    	 	edg[i]={ a,b,c};
    	 }
    	sort(edg,edg+m,cmp);
    	int t=Kruskal();
    	 if(t==INF){ 
    	 	cout<<"impossible"<<endl;
    	 }
         else{ 
         	cout<<t<<endl;
    	 }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，422人围观）

还没有评论，来说两句吧...

相关阅读

相关最小方差生成树（Kruskal）

问题描述给定带权无向图，求出一颗方差最小的生成树。输入格式输入多组测试数据。第一行为N,M，依次是点数和边数。接下来M行，每行三个整数U,V,W，代表连接U,V的边

偏执的太偏执、/ 2022年09月29日 15:51/ 0 赞/ 119 阅读

相关安慰奶牛 (Kruskal) (最小生成树)

问题描述 Farmer John变得非常懒，他不想再继续维护供奶牛之间供通行的道路。道路被用来连接N个牧场，牧场被连续地编号为1到N。每一个牧场都是一个奶牛的家。FJ计划除去

深藏阁楼爱情的钟/ 2022年09月27日 06:33/ 0 赞/ 152 阅读

相关最小生成树之kruskal算法

最小生成树之kruskal算法 1.kruskal算法假设连通网N＝（V，\{E\}）。则令最小生成树的初始状态为只有n个顶点而无边的非连通图T＝（V，\{\}）

阳光穿透心脏的1/2处/ 2022年09月25日 09:24/ 0 赞/ 177 阅读

相关最小生成树（kruskal） hdu 1233

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1233][http_acm.hdu.edu.cn_showproblem.ph

野性酷女/ 2022年08月27日 10:46/ 0 赞/ 174 阅读

相关求最小生成树Kruskal算法

求最小生成树Kruskal算法本文取自《数据结构与算法》(C语言版)(第三版)，出版社是清华大学出版社。本博文作为学习资料整理。源代码是VC++ 6.0上可执行程

古城微笑少年丶/ 2022年08月21日 04:19/ 0 赞/ 174 阅读

相关最小生成树的Kruskal算法

Kruskal算法的主要思想是按照边的权重顺序（从小到大）处理他们，将边加入最小生成树中，加入的边不会和已经加入的边构成环，直到树中含有V-1条边为止。 Kruskal算法能

Myth丶恋晨/ 2022年08月18日 11:57/ 0 赞/ 178 阅读

相关笔记：最小生成树——Kruskal算法

/\最小生成树——Kruskal算法思想：要连接n个城镇，则最少需要n-1条边，也就意味着每两个结点之间都有一条边，可以先用一个结构体数组记录边的信息，然后每次在选

深藏阁楼爱情的钟/ 2022年06月17日 02:44/ 0 赞/ 214 阅读

相关最小生成树,kruskal

最小生成树, 利用全部n个点,n-1条边建成权值最小是的树, 在无向图中选点选边, 利用并查集思想,贪心, 附上并查集思想：如果你是你爸爸,返回你,否则返回寻找你爸

喜欢ヅ旅行/ 2021年12月22日 02:55/ 0 赞/ 231 阅读

相关最小生成树（prim和kruskal）

最小生成树（prim和kruskal）最小生成树的最优子结构性质设一个最小生成树是T。如果选出一个T中的一条边，分裂成的两个树T1，T2依然是它们的点集组成的最

墨蓝/ 2021年09月30日 12:14/ 0 赞/ 377 阅读

相关最小生成树（kruskal）

伪代码 res 最小生成树中的权重之和 cnt 当前加了多少条边将所有边按权重排序O(mlogm) 枚举每条边（并查集应用）

比眉伴天荒/ 2021年06月22日 15:37/ 0 赞/ 423 阅读