图论算法-最小生成树
2021/6/20 20:26:53
本文主要是介绍图论算法-最小生成树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1.概念
对连通图进行遍历,过程中所经过的边和顶点的组合可看做是一棵普通树,通常称为生成树。
连通图中的生成树必须满足以下 2 个条件:
- 包含连通图中所有的顶点;
- 任意两顶点之间有且仅有一条通路;
所有生成树中权值最小的叫做 最小生成树。
对应地,非连通图中的类似概念为生成森林。
2.算法
1.Prim算法
1.思路:
1.反正都要经过所有点,所以先选定一个起点;
2.设置一个dist数组,表示以i为终点的邻接边的最小权值;
3.遍历当前起点的所有邻接边,按2中的含义更新dist;
4.下一次的起点为dist中的最小值对应的终点。当然,只能在没访问过的点中寻找;
5.按照如上方式,直至遍历完所有节点为止。
核心代码:
#define long long long void add(int st,int end,int w,int m) { G[m].next=first[st]; G[m].to=end; G[m].wei=w; first[st]=m; } //注意:找最小边时必须确保没访问过 int find_min() { long minn=INF; int mini=n+1; for(int i=1; i<=n; i++) { if(dist[i]<minn&&!vis[i]) { minn=dist[i]; mini=i; } } return mini; } long prim(int st) { int tot=1; //tot:已经访问结点数 long res=0; vis[st]=1; //以上为预处理起点 while(tot<n) { //遍历完所有边,即为找到一棵最小生成树 st=find_min(); //查找最小值,这里可以用堆优化 if(st==n+1) continue; res+=dist[st]; for(int i=first[st]; i!=-1; i=G[i].next) { if(dist[G[i].to]>G[i].wei&&!vis[G[i].to]) dist[G[i].to]=G[i].wei; //这是与Dijkstra的最大不同,因为要找的是邻接的边 } vis[st]=1; tot++; } return res; }
Prim算法的核心思想就是反复寻找某个点的邻接边的最小值。如果图比较稀疏,那么就不是很合适了。
例题链接
思路:直接套用模板即可,注意处理可能存在的自环和重边。
我一开始是用邻接矩阵做的,但效率比较低,关键还浪费空间。后来采用向前星就好了。但在处理自环和重边那里又卡了一下,其实建图时遇到重边无需直接舍弃,在初始化dist数组时动手脚即可,详见代码:
#include <cstdio> #include <algorithm> #define long long long #define INF 0x3f3f3f3f const int MAX_NODE=5001,MAX_EDGE=200001; using namespace std; struct graph { int next,to,wei; graph() {next=to=-1,wei=INF;} } G[MAX_EDGE*2]; //注意是无向边 int first[MAX_NODE]; int n,dist[MAX_NODE]; bool vis[MAX_NODE]; //dist为以i为终点的邻接的最小权值 void add(int st,int end,int w,int m) { G[m].next=first[st]; G[m].to=end; G[m].wei=w; first[st]=m; } //注意:找最小边时必须确保没访问过 int find_min() { long minn=INF; int mini=n+1; for(int i=1; i<=n; i++) { if(dist[i]<minn&&!vis[i]) { minn=dist[i]; mini=i; } } return mini; } //首先假定一个起点,这里为1 long prim(int st) { int tot=1; //tot:已经访问结点数 long res=0; vis[st]=1; //以上为预处理起点 while(tot<n) { //遍历完所有边,即为找到一棵最小生成树 st=find_min(); //查找最小值,这里可以用堆优化 if(st==n+1) continue; res+=dist[st]; for(int i=first[st]; i!=-1; i=G[i].next) { if(dist[G[i].to]>G[i].wei&&!vis[G[i].to]) dist[G[i].to]=G[i].wei; //这是与Dijkstra的最大不同,因为 } vis[st]=1; tot++; } return res; } //假定起点为1 int main() { int m,t=0; scanf("%d%d",&n,&m); fill(dist+1,dist+n+1,INF); fill(first,first+n+1,-1); for(int i=0; i<m; i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); if(u!=v) { add(u,v,w,t++); add(v,u,w,t++); } } for(int i=first[1]; i!=-1; i=G[i].next) dist[G[i].to]=min(dist[G[i].to],G[i].wei); //可能有重边 long res=prim(1); res!=0?printf("%lld",res):printf("orz"); return 0; }
这篇关于图论算法-最小生成树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)