Boruvka算法求最小生成树

2021年8月26日 | 分类: 【概念】

参考：https://www.cnblogs.com/guanlexiangfan/p/15178069.html
参考：https://blog.csdn.net/win_star_/article/details/106139956

算法的核心思想是贪心，类似于 kruskal

算法过程：

1. 维护途中所有联通块，然后遍历所有点和边。
2. 找到每一个联通块和其他联通块相连的最小的一条边。
3. 把连通块合并起来，重复操作，直到剩下一整个连通块。

复杂度分析：

复杂度是 O((m+n)log⁡n) ，每次合并两个连通块，进行 log 次就能完成。

【代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int nxt[N],ver[N],tot,edge[N],head[N];
int n,m,fa[N],mn[2][N],ans;
/*
mn第一维存fx这个节点距离其他节点最小的长度
第二维存当前连通块的缩点的点
*/
void add(int x,int y,int z){
    ver[++tot]=y; edge[tot]=z; nxt[tot]=head[x]; head[x]=tot;
}
int get(int x){
    if(x==fa[x]) return x;
    else return fa[x]=get(fa[x]);
}
void merge(int x,int y){
    int fx=get(x),fy=get(fy); fa[fx]=fy;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1,x,y,z;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z);
    }
    while(1){
        memset(mn[0],127,sizeof(mn[0])); bool flag=0;
        for(int x=1;x<=n;x++)
            for(int i=head[x];i;i=nxt[i]){
                int y=ver[i],fx=get(x),fy=get(y);
                if(fx==fy) continue;
                if(mn[0][fx]>edge[i]){
                    mn[0][fx]=edge[i];
                    mn[1][fx]=fy;
                }
            }
        for(int i=1;i<=n;i++)
            if(mn[0][i]!=mn[0][0]&&get(i)!=get(mn[1][i]))
                flag=1,ans+=mn[0][i],merge(i,mn[1][i]);
        if(!flag) break;
 
    }
    for(int i=1;i<n;i++) if(get(i)!=get(i+1)){
        puts("NO"); return 0;
    }
    cout<<ans<<endl;
    return 0;
}