[数据结构与算法]图论 最小生成树 Boruvka算法

一、前导

1.Kruskal和Prim的回顾

首先我们对$Kruskal$和$Prim$u算法进行回顾：

• $Kruskal$算法的基本思想是维护一个森林，查询两个结点是否在同一棵树中，并连接两棵树。在实际的算法过程中，我们需要对边集进行排序，复杂度$O(m\log m)$，并使用$O(m\log n)$并查集维护集合。总复杂度$O(m\log m)$。因此对于稠密图，$Kruskal$显得有些"水土不服"。
• $Prim$算法的基本思想是每次需要寻找距离最小的一个结点(与Dijkstra’s Algorithm相似)，以及新的边来更新其它结点的距离。在寻找距离最小点的过程中，可以暴力查找，也可以采用堆维护进行优化。在使用二叉堆优化的加持下，复杂度$O((n+m)\log n)$。相比于$Kruskal$，$Prim$更适用于稠密图。

对于最小生成树，我们一般将这类问题进行分类，对于稀松图选择$Kruskal$求解，对于稠密图则使用$Prim$算法进行求解。

2.Boruvka算法引入

很容易发现，对于某些毒瘤的问题，边的数量极其大，而边集内部又存在各种规律可能需要套上各种数据结构加以优化。但是此时$Kruskal$和$Prim$并不能很好的嵌合进这些数据结构。此时我们可以引入$Boruvka$算法。

对于$Boruvka$算法，一个比较笼统的表述是，一个多路增广版本的$Kruskal$。它的思想是一开始所有点看做独立子集，每次遍历边找到两个集合(连通块)之间连接的最短边，不断扩大集合(连通块)直到所有点合并为一个集合(连通块)。

二、Brouvka原理与实现

1.基本原理

在并查集算法中，初始状态下我们将每个点视为一个独立的点集，并不断地合并集合。在$Brouvka$算法中，我们在一开始将所有点视为独立子集，每次我们找到两个集合(即为连通块)之间的最短边，然后扩展连通块进行合并。

可以发现，$Boruvka$算法将求解最小生成树的问题分解为求连通块间最小边的问题。它的基本思想是：

生成树中所有顶点必然是连通的，所以两个不相交集必须连接起来才能构成生成树，而且所选择的连接边的权重必须最小，才能得到最小生成树。

2.基本过程

1. 首先将所有点视为各自独立的集合，初始化一个空的$MST$;
2. 当子集个数大于$1$的时候，对各个子集和执行以下操作：
   1. 找到与当前集合有边的集合，选出权值最小的边；
   2. 如果该权值最小的边不在$MST$中；

3.实现

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
const int M = 1e6 + 10;

struct node { int u, v, w; } edge[M];

int f[N], best[N];
bool vis[N];
int n, m;

int find(int x){
    return f[x] == x ? x : find(f[x]);
}

inline const bool cmp(int u, int v){
    if(v == 0) return 1;
    if(edge[u].w != edge[v].w) return edge[u].w < edge[v].w;
    return u < v;
}

inline void init(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++) cin >> edge[i].u >> edge[i].v >> edge[i].w;
    for(int i = 1; i <= n; i++) f[i] = i;
}

inline int boruvka(){
    memset(vis, 0, sizeof(vis));
    int ans = 0, cnt = 0;
    bool status = true;
    while(true){
        status = false;
        //遍历边集
        for(int i = 1; i <= m; i++){
            if(!vis[i]){
                int uu = find(edge[i].u), vv = find(edge[i].v);
                if(uu == vv) continue;
                if(cmp(i, best[uu])) best[uu] = i;
                if(cmp(i, best[vv])) best[vv] = i; 
            }
        }
        //遍历点集
        for(int i = 1; i <= n; i++){
            if(best[i] && !vis[best[i]]){
                status = true, cnt++, ans += edge[best[i]].w;
                vis[best[i]] = 1;
                int uu = find(edge[best[i]].u), vv = find(edge[best[i]].v);
                f[uu] = vv;
            }
        }
    }
    if(cnt == n - 1) return ans;
    return -1;
}

signed main(){
    init();
    boruvka();
    return 0;
}