Borůvka算法笔记

发表于2020-10-08更新于2023-09-17字数统计1.3k阅读时长12分作者Shane

求最小生成树常用算法有 KruskalKruskal 和 PrimePrime 算法，下面介绍第三种求最小生成树的算法 —— Boru˚vkaBorůvka。

算法的执行流程如下：

  1. 对每一个连通块，记录不在生成树中，从这个块出发，能到达别的联通块的长度最小的边。（注：长度相同选编号小的边，保证两个联通块互连时选的边是一致的，否则有可能出现环）

  2. 将上一步选中的边加入最小生成树。

  3. 重复上述步骤，直到没有边可以加入。

动图

Boru˚vkaBorůvka 算法演示动图如上（源：Wikimedia)

由于每次合并的时间复杂度为 O(M+N)O(M+N)，每次合并后，连通块的个数减少一半，因此总的时间复杂度是 O((M+N)logN)O((M+N)logN) 的。

例题

P3366 模板-最小生成树

Description

题目链接

Solution

用并查集容易实现上述过程。对于图的连通性的判断，可以开一个变量记录加入边的总数，如果总数不是 n−1n-1 说明图不连通。

Code

模板-最小生成树
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>

using namespace std;

int n, m, u, v, fa[5005], miEdge[5005];
bool used[200005];

template <class T>
void read(T& x, T f = 1, char ch = getchar()) {
    x = 0;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

struct Egde {
    int to, from, len;
} e[200005];

int find(int x) {
    if (fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}

void Boruvka() {
    int merged = 0;
    long long sum = 0;
    for (int i = 1; i <= n; i++) fa[i] = i;

    bool tag = true;
    while (tag) {
        tag = false;
        fill(miEdge + 1, miEdge + n + 1, 0);
        for (int i = 1; i <= m; i++) {
            if (used[i]) continue;
            int r1 = find(e[i].from), r2 = find(e[i].to);
            if (r1 == r2) continue;
            if (!miEdge[r1] || e[i].len < e[miEdge[r1]].len) miEdge[r1] = i;
            if (!miEdge[r2] || e[i].len < e[miEdge[r2]].len) miEdge[r2] = i;
        }
        for (int i = 1; i <= n; i++) {
            if (miEdge[i] && !used[miEdge[i]]) {
                tag = true;
                merged++;
                int eid = miEdge[i];
                sum += e[eid].len;
                used[eid] = 1;
                fa[find(e[eid].from)] = find(e[eid].to);
            }
        }
    }
    if (merged == n - 1)
        cout << sum;
    else
        cout << "orz";
}

int main() {
    read(n), read(m);
    for (int i = 1; i <= m; i++) read(e[i].from), read(e[i].to), read(e[i].len);
    Boruvka();
    return 0;
}

CF888G Xor-MST

题目链接

Description

给出完全图 KnK_n，任意两点 i,ji,j 的边权为 ai⊕aja_i ⊕ a_j，求该图的最小生成树。

Solution

由于边有 n∗(n+1)/2n*(n+1)/2 条，因此考虑使用 Boru˚vkaBorůvka 算法，同时设法快速找到不在生成树中，从这各个联通块出发能到达别的联通块的长度最小的边。

对所有节点建立一个全局 trietrie，同时对每个联通块各自维护一个 trietrie。求不属于某一联通块的最小的边可以通过在全局 trietrie 和当前连通块的 trietrie 上对 sizesize 作差贪心地求得，而加入一条边就是将两个 trietrie 合并。上述解法时间复杂度是 O(nlognlogmax⁡i=1na[i])O(nlog{n}log{\max\limits_{i=1}^{n}a[i]})。

Code

Xor-MST
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2E5 + 5;
int n, m, a[MAXN], fa[MAXN], root[MAXN], minEdge[MAXN], nxt[MAXN];

template <class T>
void read(T& x, T f = 1, char ch = getchar()) {
    x = 0;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

struct Trie {
    int son[2], sz, id;
    Trie() { son[0] = son[1] = sz = id = 0; }
} tr[MAXN * 31 * 2];

void insert(int root, int id) {
    static int cntNode = n + 1;
    int cur = root;
    for (int i = 30; ~i; i--) {
        int to = (a[id] >> i) & 1;
        if (!tr[cur].son[to]) tr[cur].son[to] = ++cntNode;
        cur = tr[cur].son[to];
        tr[cur].sz++;
    }
    tr[cur].id = id;
}

int merge(int root1, int root2) {
    if (!root1 || !root2) return root1 + root2;
    tr[root1].sz += tr[root2].sz;
    for (int i = 0; i < 2; i++)
        tr[root1].son[i] = merge(tr[root1].son[i], tr[root2].son[i]);
    return root1;
}

int query(int root1, int root2, int val) {
    for (int i = 30; ~i; i--) {
        int to = (val >> i) & 1;
        if (tr[tr[root1].son[to]].sz > tr[tr[root2].son[to]].sz)
            root1 = tr[root1].son[to], root2 = tr[root2].son[to];
        else
            root1 = tr[root1].son[to ^ 1], root2 = tr[root2].son[to ^ 1];
    }
    return tr[root1].id;
}

int find(int x) {
    if (fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}

void Boruvka() {
    long long sum = 0;
    for (int i = 1; i <= n; i++) fa[i] = i, insert(root[i], i);
    bool tag = true;
    while (tag) {
        tag = false;
        fill(minEdge + 1, minEdge + n + 1, -1);
        for (int i = 1; i <= n; i++) {
            int r1 = find(i);
            int id = query(root[0], root[r1], a[i]);
            if (!id) continue;
            int len = a[id] ^ a[i];
            int r2 = find(id);
            if (minEdge[r1] == -1 || len < minEdge[r1])
                minEdge[r1] = len, nxt[r1] = r2;
            if (minEdge[r2] == -1 || len < minEdge[r2])
                minEdge[r2] = len, nxt[r2] = r1;
        }
        for (int i = 1; i <= n; i++) {
            if (minEdge[i] != -1 && find(i) != find(nxt[i])) {
                tag = true;
                merge(root[find(i)], root[find(nxt[i])]);
                sum += minEdge[i];
                fa[find(nxt[i])] = i;
            }
        }
    }
    cout << sum;
}

int main() {
    read(n);
    for (int i = 1; i <= n; i++) read(a[i]);
    sort(a + 1, a + n + 1);
    for (int i = 0; i <= n; i++) root[i] = i + 1;
    for (int i = 1; i <= n; i++) insert(root[0], i);
    Boruvka();
    return 0;
}