生成树算法总结(Prim,Kruskal,Boruvka)

前言

其实原理都很简单

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 ;
}