最小生成树算法Kruskal
2021/7/6 22:10:11
本文主要是介绍最小生成树算法Kruskal,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录- 最小生成树算法
- 1、Kruskal
- 1.1 算法简介
- 1.2 C++实现
- 1、Kruskal
最小生成树算法
最小树定义:
- 给定网络\(G=(N,E,W)\),设\(T=(N,E')\)为\(G\)的一个支撑树,令\(W(T)=\sum_{e\in E'}W(e)\)为\(T\)的权(或长)。\(G\)中权最小的支撑树称为\(G\)的最小树。
1、Kruskal
- 并查集:用一个元素代表一组元素,用于查询不同元素是否属于同一组,以及合并组
int par[MAXN];//每个元素所在集合代表元素的编号 int rnk[MAXN];//所在集合的大小; //初始化 for(int i=0; i<n; i++){ par[i]=i; rnk[i]=1; } int find(int x){ //查找x所在集合的代表元 if(par[x]==x)//到达根 return x; //直接路径压缩,忽略节点之间关系,把节点挂到根上 else par[x] = find(par[x]); } bool unite(int x,int y){ //把一个分组挂到另一个分组,返回合并是否成功 x=find(x); y=find(y); if(x == y) return false; if(rnk[x]>rnk[y]){//把小树挂在大树上,防止出现高树 par[y]=x; rnk[x] = (rnk[y] += rnk[x]); //可以直接rnk[x]+=rnk[y] } else{ par[x]=y; rnk[y] = (rnk[x] += rnk[y]); //可以直接rnk[y]+=rnk[x] } return true; }
1.1 算法简介
Kruskal是1956年首次提出的求最小生成树的算法,后来Edmonds把该算法称为贪心算法,其基本思路就是从G中的m条边中选取n-1条权尽可能小的边,使其不构成回路,从而构成一个最小树。
- 第一步:把图按照边权的大小从小到大排列起来,初始化一个已选中的边集,或计数器
- 第二步:不断从加入之后不构成环的边中选择权最小的边加入边集
- 第三步:如果边集中边的数量达到n-1,则停止,否则继续选边加边
1.2 C++实现
#include<bits/stdc++.h> using namespace std; const int MAXN = 1e6; struct edge{ int u,v,w; //重载比较符,为了按照边权排序 bool operator < (const edge& t){ return w < t.w; } }e[MAXN]; int m,n; int par[MAXN];//每个元素所在集合代表元素的编号 int rnk[MAXN];//所在集合的大小; void init(int n){ for(int i=0; i<n; i++) par[i]=i; } int find(int x){ if(par[x]==x) return x; else par[x] = find(par[x]); } bool unite(int x,int y){ x=find(x);y=find(y); if(x == y) return false; par[x]=y; return true; } int kruskal(){ std::sort(e+1,e+1+m); int cnt=0,minum_tree_size=0; for(int i=1; i<=m; i++){ if(unite(e[i].u,e[i].v)){ minum_tree_size += e[i].w; if(++cnt == n-1)break; } } return cnt==n-1? ans : -1; } int main(){ scanf("%d%d", &m,&n); init(n); for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); printf("%d\n",kruskal()) return 0; }
这篇关于最小生成树算法Kruskal的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现