当前位置:网站首页>最小生成树
最小生成树
2022-08-01 07:05:00 【bj_hacker】
介绍
之前讲过最短路,是求两点之间的最短路径。
最小生成树,是指有n条边,m个点(n>=m),寻任意条边,连接每一个点,使边权之和最小; 保证有解 {保证有解} 保证有解
分析
因为需要连接m个点,我们要做的就是找出n-1条边,无环,且能连接m个点,还保证边权和最小。
如何去做呢?
提供2个算法Prim和Kruskal
算法
Prim
主要思想
一开是分两个集合S和T
S表示已确定的最小生成树点,T表示未扩展的点,lowcost[i]表示i点S集合的最近距离。
循环n-1次
每次遍历其他所有节点
如果该点未在S集合中且距离S集合的距离最小,记录
加入S集合
更新T集合点到S集合的距离
完美图解
模板代码(无优化)
void Prim(int n){
//初始化
s[1]=true;
for(int i=1;i<=n;i++){
if(i!=1){
lowcost[i]=c[1][i];
closest[i]=1;
s[i]=false;
}
else lowcost[i]=0;
}
//n-1条边的添加
for(int i=1;i<n;i++){
int temp=inf;
int t=1;
//寻找离已添加最近的节点t
for(int j=1;j<=n;j++){
if(!s[j]&&lowcost[j]<temp){
temp=lowcost[j];
t=j;
}
}
if(t==1)break;
s[t]=true;
//更新未添加节点
for(int j=1;j<=n;j++){
if(!s[j]&&c[t][j]<lowcost[j]){
lowcost[j]=c[t][j];
closest[j]=t;
}
}
}
}
复杂度
暴力:O(n^2+m)
二叉堆:O((n+m)*log(n)
Fib 堆:O(n*log(n)+m)
Kruskal
主要思想
Kruskal 算法是一种常见并且好写的最小生成树算法,由 Kruskal 发明。该算法的基本思想是从小到大按边权排序,判断不是在同一集合的加入边集合,是个贪心算法。
(ps:运用到了并查集:https://blog.csdn.net/weixin_42178241/article/details/126013714)
完美图解
模板代码(无优化)
//边集数组
struct node {
int u,v,w;
}e[maxn];
//排序优先级,边权从小到大
bool cmp(node x,node y){
return x.w<y.w;
}
//初始化
void init(int n){
for(int i=1;i<=n;i++)fa[i]=i;
}
//合并
int merge(int a,int b){
int p=fa[a];
int q=fa[b];
if(p==q)return 0;
//不是同一祖先,合并赋值
for(int i=1;i<=n;i++){
if(fa[i]==q)fa[i]=p;
}
return 1;
}
//求最小生成树
int Kruskal(int n){
int ans=0;
sort(e,e+m,cmp);
for(int i=0;i<m;i++){
if(merge(e[i].u,e[i].v)){
ans+=e[i].w;
n--;
//共执行n-1次合并,n=1时算法结束
if(n==1)return ans;
}
}
return 0;
}
复杂度
O(m*log(m))
边栏推荐
猜你喜欢
随机推荐
从底层结构开始学习FPGA(6)----分布式RAM(DRAM,Distributed RAM)
rhcsa 第四天
flinkcdc对mysql的date字段类型转化有什么解决思路么
mysql的行锁和间隙锁
R语言使用gt包和gtExtras包优雅地、漂亮地显示表格数据:gtExtras包的pad_fn函数与gt::fmt函数一起用于填充包含数值的特定列、对数据列的数值进行十进制对齐(从小数点对齐)
我三本学历,五面阿里,被面试官“供”着出来了,拿了33*15的Offer
Detailed explanation of the crawler framework Scrapy
Datagrip error "The specified database userpassword combination is rejected..."Solutions
【视觉SLAM十四讲】第一章理论详解
奇葩问题 npm install 报错 gyp ERR
Classwork (7) - #598. remainder operation (mod)
日志导致线程Block的这些坑,你不得不防
Three aspects of Ali: How to solve the problem of MQ message loss, duplication and backlog?
Fist game copyright-free music download, League of Legends copyright-free music, can be used for video creation, live broadcast
权重等比分配
滚动条样式修改
How to use Photoshop to composite star trail photos, post-processing method of night sky star trail photos
GO错误处理方式
实战演练 Navicat 中英文模式切换
datagrip 报错 “The specified database userpassword combination is rejected...”的解决方法