浅谈三种求最小生成树的方法

本篇⽂章的定义均来⾃于定义

我们定义⽆向连通图的 最⼩⽣成树 （Minimum\\ Spanning\\ Tree,MST）为边权和最⼩的⽣成树。注意：只有连通图才有⽣成树，⽽对于⾮连通图，只存在⽣成森林。Prim算法

Prim 算法是⼀种常见并且好写的最⼩⽣成树算法。该算法的基本思想是从⼀个结点开始，不断加点具体来说，每次要选择距离最⼩的⼀个结点，以及⽤新的边更新其他结点的距离时间复杂度 O(n^2)#include#include#include#include#define rg registerinline int read(){ rg int x=0,fh=1;

rg char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') fh=-1; ch=getchar(); }

while(ch>='0' && ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

return x*fh;}

const int maxn=5e3+5;

int mp[maxn][maxn],dis[maxn],n,m;bool vis[maxn];void prim(){ dis[1]=0;

for(rg int i=1;ifor(rg int j=1;j<=n;j++){

if(!vis[j] && (x==0 || dis[j]vis[x]=1;

for(rg int j=1;j<=n;j++){

if(!vis[j]) dis[j]=std::min(dis[j],mp[j][x]); } }}

int main(){

memset(mp,0x3f,sizeof(mp)); memset(dis,0x3f,sizeof(dis)); n=read(),m=read(); rg int aa,bb,cc;

for(rg int i=1;i<=m;i++){

aa=read(),bb=read(),cc=read();

mp[aa][bb]=mp[bb][aa]=std::min(mp[aa][bb],cc); }

prim();

rg int ans=0;

for(rg int i=1;i<=n;i++){ ans+=dis[i]; }

printf(\"%d\\n\ return 0;}

Kruskal 算法

Kruskal 算法是另⼀种常见并且好写的最⼩⽣成树算法，由 Kruskal 发明该算法的基本思想是从⼩到⼤加⼊边，是个贪⼼算法时间复杂度 O(mlogn)#includeusing namespace std;const int maxn=600000;struct asd{

int from,to,val;}b[maxn];

int tot=1,head[maxn];

void ad(int aa,int bb,int cc){ b[tot].from=aa; b[tot].to=bb; b[tot].val=cc; tot++;}

bool cmp(asd aa,asd bb){ return aa.val}

int fa[maxn];int zhao(int xx){

if(xx==fa[xx]) return xx; return fa[xx]=zhao(fa[xx]);}

void bing(int xx,int yy){ fa[zhao(xx)]=zhao(yy);}

int shu(int xxx){

sort(b+1,b+tot,cmp); int ans=0,cnt=0; for(int i=1;iint xx=b[i].from,yy=b[i].to; if(zhao(xx)!=zhao(yy)){ bing(xx,yy); ans+=b[i].val;

if(++cnt==xxx) return ans; } }

return -1;}

int main(){

for(int i=0;iscanf(\"%d%d\ for(int i=1;i<=m;i++){ int aa,bb,cc;

scanf(\"%d%d%d\ ad(aa,bb,cc); }

int ans=shu(n-1);

if(ans==-1) printf(\"orz\\n\"); else printf(\"%d\\n\ return 0;}

Boruvka 算法

Boruvka 其实是⼀种多路增⼴的 Prim

Boruvka 算法每⼀次的增⼴，会对现在的每⼀个连通块都找⼀遍的最短边，最后每个连通块择优，将这些边全部连上时间复杂度 O(mlogn)#include#include#include#define rg registerinline int read(){ rg int x=0,fh=1;

rg char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') fh=-1; ch=getchar(); }

while(ch>='0' && ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

return x*fh;}

const int maxn=1e6+5;struct asd{ int zb,yb,val;}b[maxn];

int n,m,fa[maxn],cnt,sum,bes[maxn];int zhao(rg int xx){

if(xx==fa[xx]) return xx; return fa[xx]=zhao(fa[xx]);}

bool vis[maxn];

bool pd(rg int aa,rg int bb){ if(bb==0) return 1;

if(b[aa].val!=b[bb].val) return b[aa].valint main(){

n=read(),m=read(); for(rg int i=1;i<=m;i++){

b[i].zb=read(),b[i].yb=read(),b[i].val=read(); }

for(rg int i=1;i<=n;i++) fa[i]=i; rg bool jud=1;

rg int aa,bb; while(jud){ jud=0;

memset(bes,0,sizeof(bes)); for(rg int i=1;i<=m;i++){ if(vis[i]) continue;

aa=zhao(b[i].zb),bb=zhao(b[i].yb); if(aa==bb) continue;

if(pd(i,bes[aa])) bes[aa]=i; if(pd(i,bes[bb])) bes[bb]=i; }

for(rg int i=1;i<=n;i++){

if(bes[i]!=0 && vis[bes[i]]==0){ jud=1; cnt++;

sum+=b[bes[i]].val; vis[bes[i]]=1;

fa[zhao(b[bes[i]].zb)]=zhao(b[bes[i]].yb); } } }

if(cnt!=n-1) printf(\"orz\\n\"); else printf(\"%d\\n\ return 0;}