Boruvka 算法可谓 Prim 算法和 Kruskal 算法的结合体……
Part1. 初识 Boruvka
对于生成树算法,我们最先想到的是 ① 从最小边开始加边的 Kruskal、② 从当前构造出的树向外扩展的 Prim ……
而 Boruvka 算法是两者的结合体,可能因为这个算法太像 Kruskal 和 Prim 了……它一直比较冷门。但是,用到这个算法的好题也不少。总而言之还是学一下好了。
Boruvka 算法的一句话思想便是:
“从所有当前的连通块向其他连通块扩展出最小边,直到只剩一个连通块”,其中取最小边的贪心思想是 Kruskal 的主体,而向外扩展又是 Prim 的思想 —— 基于另外两种生成树算法,Boruvka 的正确性显然。
Part2. Boruvka 的实现
其实代码框架非常浅显易懂:
1 | while 连通块个数>1 |
其中最为重要的是求 mn[i]
,可能会以其他各种算法辅助求解,这也是出题人设题的主要考察点。
由于每进行一次操作,连通块个数会减少一半,因此(如果记 $O(T)$ 是计算 mn[]
的复杂度)这个算法的复杂度是 $O(T\log_2N)$。最朴素的求 mn[]
的方法是 $O(M)$ 枚举边,如果可以优化这一步骤,效率会大大提高。
>> 个人看法
考察 Boruvka 算法的题目大多数会在求解
mn[]
这里设置难度,比如让边数超级大……因此很多的题目都是“给出一种计算两点之间边权的方式,求一个完全图的生成树”。这样的话 $O(M)$ 即 $O(N^2)$,大多数题目是过不了的……
Part3. 例题 - XOR MST (CF 888G)
下面让我们来看看一道非常好的例题(别的算法的版子题都非常水,唯有 Boruvka 极其恶心……)
Part3/1. 题面
有 n 个点构成一个完全图,每个点的点权为 $a_i$,连接 i,j 的边的权值为 $a_i\oplus a_j$ (异或)。求最小生成树。
$1\le n\le2\times10^5,0\le a_i\le2^{30}$
Part3/2. 解析
你看它是一个完全图……非常适合 Boruvka,于是就想怎么求 mn[]
。也就是说对于一个连通块 S,求 $i\in S,j\not\in S$ 的 $a_i\oplus a_j$ 的最小值。
对于异或最小值,我们有两种常见的处理方法 —— 线性基、字典树。然而在合并两个连通块的时候,如果用线性基,不止要合并两个连通块的线性基,还要从不属于该连通块的线性基中删除……(线性基不支持删除,但是字典树可以)
于是考虑先建出所有 $a_i$ 的字典树。当我们询问连通块 S 的 mn[S]
时,将 $a_i (i\in S)$ 在字典树中删掉,然后对于每个 $a_i$ ($i\in S$) 在字典树里贪心地求一个异或最小值,更新 mn[S]
。计算完 mn[S]
后,再把 $a_i$ $(i\in S)$ 重新插入字典树。
一次字典树的操作是 $O(\log_2 a_i)$ 的,每次求 mn[]
时会遍历所有 $n$ 个点一次(因为每个点都属于恰好一个连通块)。因此求一次 mn[]
是 $O(n\log_2 a_i)$ 的。套上 Boruvka 的复杂度,总体复杂度就是 $O(n\log_2 n\log_2a_i)$(小心卡常)。
Part3/3. 源代码
1 | /*Lucky_Glass*/ |
The End
Thanks for reading!
你已经理解了 Boruvka 了?