首页 > 代码库 > 最小生成树
最小生成树
最小生成树
Prim
时间复杂度O(n2)
蓝白点思想，蓝点代表为纳入最小生成树的点，白点代表已纳入的点。
初始化所有点到最小生成树的距离；（极大值）
选择一个点作为树的根节点；（没有要求的话，一般选择第一个点）
枚举该点出发的所有边，进行松弛操作，并将该点标为白色；
从蓝点中选取离最小生成树最近的点进行松弛操作，并加入最小生成树；
如此循环，直到所有点都加入最小生成树；
例题：【模板】最小生成树
算法结束。
#include<cstdio>#include<iostream>using namespace std;const int inf=100000000;int n,ans,p,b;int a[110],map[110][110];bool v[110];int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&map[i][j]); for(int i=1;i<=n;i++) a[i]=map[1][i]; v[1]=1; for(int i=1;i<n;i++){ p=inf; for(int i=1;i<=n;i++) if(!v[i]&&a[i]<p){p=a[i];b=i;} ans+=a[b];v[b]=1; for(int i=1;i<=n;i++) a[i]=min(a[i],map[b][i]); } printf("%d\n",ans); return 0;}
Kruskal
时间复杂度O(eloge)
加边法。
首先，对所有边进行排序，时间复杂度O(eloge)；
从小到大枚举边，如果边的两端已经处于同一个集合，加入该边，否则不加入。
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 int n,m,a,b,ans; 5 int fa[5010]; 6 struct nate{ 7 int q,z,bq; 8 }edge[200010]; 9 int comp(const nate&x,const nate&y ){return x.bq<y.bq;}10 int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}11 int main(){12 scanf("%d%d",&n,&m);13 for(int i=1;i<=m;i++) scanf("%d%d%d",&edge[i].q,&edge[i].z,&edge[i].bq);14 sort(edge+1,edge+m+1,comp);15 for(int i=1;i<=n;i++) fa[i]=i;16 for(int i=1;i<=m;i++){17 a=find(edge[i].q);b=find(edge[i].z);18 if(a!=b){19 ans+=edge[i].bq;20 fa[b]=a;21 }22 }23 printf("%d\n",ans);24 return 0;25 }
从时间复杂度来看，两种算法各有优劣，不过在OI中，一般的图都是点多边少，所以Kruskal可能更常用一些；
最小生成树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。