【算法教程】【C/C++】最小生成树——程序设计思路与代码实现

faryou2周前 (09-22)技术教程

前言

        最小生成树是指在一个无向图内,找出一棵树,使得各个结点之间能够互相到达,且总路径长度最短。


程序设计思路

        最小生成树主要有两种思路——Kruskal和Prim,两者的时间复杂度为On2和On3,限于篇幅原因,故进行两者的讲解,只提供Kruskal的代码。

        首先讲时间复杂度较高的Prim算法(有点像dijkstra):在图中先确定一个点,将该点加入队列,之后每次循环在与队列中的所有点连接的边中找出最短边(不得与之前已经在队列中的点相连),直到所有的点都被加入队列。

        Kruskal是一种基于贪心的算法:每次在所有的边中找出最短边,判断其两端有没有与之前已经相连的点重复,直到所有点之间都已连接。因此,Kruskal需要进行排序操作。


代码实现

IMG_20240831_071633.png

        这里只放Kruskal的代码:

#include <bits/stdc++.h>

struct tree{//存边,x、y分别代表两个端点,z为边权
	int x,y,z;
}tr[200005];

int n,m,iq,aq,sb=0,bin[5005],ans=0;//n、m如题意,iq、aq分别临时存放路径,sb用于计数(只拿n-1条边),bin存放每个点的路径,ans累加长度

int find(int a){//由于Kruskal基于树进行,可以使用路径压缩,详见并查集那篇文章
	int x=a;
	if(bin[x]!=x) return bin[x]=find(bin[x]);
	else return x;
}

bool cmp(tree a,tree b){//sort升序
    return a.z<b.z;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){//读入
		scanf("%d%d%d",&tr[i].x,&tr[i].y,&tr[i].z);
		bin[tr[i].x]=tr[i].x;
		bin[tr[i].y]=tr[i].y;
	}
	sort(tr+1,tr+m+1,cmp);//升序排序
	for(int i=1;i<=m;i++){//遍历每条边
		iq=find(tr[i].x);//找当前边的x是否连入图中
		aq=find(tr[i].y);//找当前边的y是否连入图中
		if(iq==aq) continue;//当两者祖先相同时,直接跳过防止成环
		ans+=tr[i].z;//累加
		sb++;//计次
		bin[aq]=iq;//修改路径
		if(sb==n-1) break;//当要取的边数量足够时,退出循环
	}
	for(int i=1;i<n;i++) if(find(i)!=find(i+1)){//判断每个点的祖先是否相同
		printf("orz");
		return 0;
	}
	printf("%d",ans);
	return 0;
}

        这里需要注意的是,由于我们已经完成了排序,故不需要在之后判断大小。


结语

        本文中讲了Kruskal的思路及代码,并融入了并查集的知识。我是faryou,再见!

本文链接:https://blog.faryou.eu.org/post/107.html 转载需经作者授权!

分享到:

扫描二维码推送至手机访问。

版权声明:本文由faryou的博客发布,如需转载请注明出处。

本文链接:https://blog.faryou.eu.org/post/107.html

标签: C++算法基础
分享给朋友:

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。