最小生成树是图论当中的重要知识,想要解决该类问题一般是有2种算法,分别是普利姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。
1.普利姆(Prim)算法
Prim算法跟之前用来求最短路算法的Dijkstra算法极其相似,主要分为两种,分别是稠密图和稀疏图。稠密图我们可以采用朴素版的Prim算法,而稀疏图我们要使用堆优化版的Prim算法(使用频率不多,一般使用Kruskal算法),这两种的时间复杂度分别是O(n2)和O(mlogn)。
算法流程:
先将所有的距离初始化成正无穷,然后进行n次迭代,每次迭代先找到不在集合内(未标记的)的距离最小的点,然后用t更新这个点到集合的距离(Dijkstra算法中是更新这个点到起点的距离),最后将t加入到集合当中(标记t),就完成了。
代码实现:
题目大意:一个n个点m条边的无向稠密图,如果该图存在最小生成树,输出最小生成树的树边权重之和,否则输出impossible。
Code:
#include <cstring> #include <iostream> #include <algorithm> #define N 510 #define INF 0x3f3f3f3f using namespace std; int n,m; int g[N][N]; int dist[N]; bool st[N]; int prim(){ memset(dist,0x3f,sizeof dist); int res=0; for(int i=0;i<n;i++){ int t=-1; for(int j=1;j<=n;j++) if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j; if(i&&dist[t]==INF) return INF; if(i) res+=dist[t]; st[t]=true; for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]); } return res; } int main(){ scanf("%d%d",&n,&m); memset(g,0x3f,sizeof g); while(m--){ int a,b,c; scanf("%d%d%d",&a,&b,&c); g[a][b]=g[b][a]=min(g[a][b],c); } int t=prim(); if(t==INF) printf("impossible"); else printf("%d/n",t); return 0; }
2.克鲁斯卡尔(Kruskal)算法
Kruskal与并查集有点相似,一般用作稀疏图,时间复杂度为O(mlogm)。
算法流程:
1.将所有边按权重从小到大排序 时间复杂度O(mlogm)
2.从小到大枚举每条边AB,权重为C。如果AB不连通,则将这一条边加入到这个集合中来
代码实现:
题目大意:一个n个点m条边的无向稀疏图,如果该图存在最小生成树,输出最小生成树的树边权重之和,否则输出impossible。
Code:
#include <cstring> #include <iostream> #include <algorithm> #define N 100010 #define M 200010 #define INF 0x3f3f3f3f using namespace std; int n,m; int p[N]; struct Edge{ int a,b,w; bool operator<(const Edge &W)const{//重载运算符,可以写个cmp return w<W.w; } }edges[M]; int find(int x){ if(p[x]!=x) p[x]=find(p[x]); return p[x]; } int kruskal(){ sort(edges,edges+m); for(int i=1;i<=n;i++) p[i]=i;//初始化并查集 int res=0,cnt=0; for(int i=0;i<m;i++){ int a=edges[i].a,b=edges[i].b,w=edges[i].w; a=find(a),b=find(b); if(a!=b){ p[a]=b; res+=w; cnt++; } } if(cnt<n-1) return INF; return res; } int main(){ scanf("%d%d",&n,&m); for (int i=0;i<m;i++){ int a,b,w; scanf("%d%d%d",&a,&b,&w); edges[i]={a,b,w}; } int t=kruskal(); if(t==INF) printf("impossible"); else printf("%d/n",t); return 0; }
–最小生成树–最小生成树–最小生成树–最小生成树–最小生成树–最小生成树–最小生成树–最小生成树–最小生成树–
原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/tech/pnotes/276460.html