文章目录

前言PrimKruskalBoruvka

前言

其实原理都很简单

Prim

指定一个点作为原点 $s$ 向外不断连边 时间复杂度：手写堆 $O(mlogn)$ STL $mlogm$ 斐波那契堆 $O(nlogn+m)$

Kruskal

按边权连边，并查集实现 时间复杂度: $O(mlogm)$

Boruvka

多点合并，每个连通块选择最短的边往外连最短的边 时间复杂度 $O(mlogn)$

struct Edge{ int u,v,w; }edge[MAXM+5]; int mst,fa[MAXN+5],cho[MAXN+5]; inline int Find(int x){return (x==fa[x]?x:(fa[x]=Find(fa[x])));} void Boruvka(int N,int M){ int bcnt=N; for(int i=1;i<=N;i++) fa[i]=i; while(bcnt>1){ memset(cho,-1,sizeof(cho)); for(int i=1;i<=M;i++){ int fu=Find(edge[i].u),fv=Find(edge[i].v); if(fu==fv) continue; if(cho[fu]==-1||edge[cho[fu]].w>edge[i].w) cho[fu]=i; if(cho[fv]==-1||edge[cho[fv]].w>edge[i].w) cho[fv]=i; } for(int i=1;i<=N;i++){ if(cho[i]==-1) continue; int fu=Find(edge[cho[i]].u),fv=Find(edge[cho[i]].v); if(fu==fv) continue; bcnt--,fa[fv]=fu; mst+=edge[cho[i]].w; } } return ; }