0%

「进行中」Dynamic Minimum Spanning Tree

XHR 问我关于动态 MST 的问题,于是找论文看到一个很神奇的 O(sqrt(m)) per update 的方法。把思路简单说一下吧。(你可以简单地把这篇文章看成是翻译 = =||)

原论文标题是 Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications ,作者是 Greg N. Frederickson

保证每个点的度

保证每条边的权为正,这是显然的。

首先要构造一个图,使得和原图的 MST 相同,且保证每个点的度不超过 3 。

原图 G(V, E), \|V\| = n, \|E\| = m ,新图 G'(V', E'), \|V'\| = m, \|E'\| = m ,做法是将原图中的每个点拆成 D 个点(D 表示这个点的度),这 D 个点形成一个环,环上边的权为 0 ,原图的每一条边就可以对应新图一条边,而且任意两条原图的边不会占用同一个新图的点,可以保证每个点的度不超过 3 。

维护的值、可能的操作

z:块的大小

块状树的构造:

def csearch(v) :
    clust = set()
    for u in child[v] :
        clust = cluse \| csearch(u)
    if len(clust) > z :
        # find a new clust
        return set()
    return clust

E[i, j] :表示所有连接第 i 个块和第 j 个块的边

minE[i, j] :表示 E[i, j] 中权最小的边

delB(i) :删除第 i 个块。复杂度 O(z)

addB(S) :建立一个块,块内的元素集合为 S 。复杂度 O(z)

delE(x, y):删除树上连接 x 和 y 的边。如果这条边连接两个块,直接无视。否则先把两个点所在的块删除,然后和相邻的某个块合并,如果合并后的块大小超过某个值,再分裂。所有访问到的块为常数个,复杂度 O(z)

addE(x, y) :添加一条连接 x 和 y 的边,然后试图合并两个块。复杂度 O(z)

由于度数限制,每个操作的复杂度均为 O(z)

O(m^{2/3}) per update

我们用块状树维护 MST 。

有四种可能的操作:减小树边的权,增加非树边的权,减小非树边的权,增加树边的权。前两种总是可以忽略的。

对于第三种情况,直接查询最大的树边,有可能的话就把它替换掉。替换就是先删除一条边,再添加一条边。

对于第四种情况。我们先把这条树边删去,然后枚举所有的块对,如果可以覆盖这条边,那么用 minE[i, j] 来更新最优的非树边。最后再比较一次,如果可以更新 MST 就执行一次替换。

复杂度的事呢,第三种情况显然是 O(z) 的,第四种情况是 O(z + (m/z)^2) 的,于是 z = m^{2/3} 好了。

O(sqrt(m log m)) per update

上述做法没有用到任何数据结构维护。一个显然的优化是用某种奇怪的数据结构来优化。

Topology Tree

这里用到的数据结构是 Topology Tree 。Topology Tree 是一种动态树,他用一个奇怪的树形结构来维护原来的树,可以在 O(log m) 的时间内往原树加入、删除一条边。

考虑一棵任意点度数不超过 3 的树,我们可以 O(n) 构造它的 Topology Tree 。具体构造方式,自己参考论文吧,因为要用图来解释我就懒得搞了。

容易证明, Topology Tree 的高度是 O(log n) 的。Topology Tree 中任意一个节点的孩子数不超过 4 。

为啥这里需要 Topology Tree 呢?因为后面需要支持若干个操作: 1. 合并两棵树 2. 把一棵树分成两棵 3. 查询一棵树的最小权

块树

构造一个新树叫做“块树”,也就是把原树一个块缩为一个点。可以得到块树的大小是 O(m / z) 的。

很囧的一点,块树的度数并没有保证。于是我们要找到一个合适的划分块的方式,使得满足: 1. 在 MST 中,任意一个块至多与三个块相邻。 2. 任意一个大小小于 z 的块必定与三个块相邻。

这种划分块的方式只要在 csearch 的基础上稍稍修改即可。每次函数再多返回一个值,表示与几个块相邻。一旦块的大小超过 z 或者度数等于 3 ,这就应该要被分成一个块。可以证明,这种方式可以满足要求。(证明懒得看了)

我们把这种划分的方式成为 度限制划分 (自己随口 YY 的名字)。

具体做法

我们在度限制划分时会产生 O(m / z) 个小块,对于每个小块我们构造一棵 Topology Tree 。这棵 Topology Tree 的每个叶子表示一个划分出来的小块,顺便用一个堆按边权大小维护 E[i, j] 以及最小权的边;对于每个内节点,我们维护这棵子树内的最小权的边。很显然,所有的 O(m / z) 棵 Topology Tree 的形状是一模一样的,只是要维护的值不一样。空间复杂度易知为 O(m^2/z^2 + m) 。当 z > sqrt(m) 时,空间复杂度为 O(m)

再次考虑删除(添加)一个块需要做的操作。每次需要修改 O(m / z) 棵 Topology Tree 。每次修改需要修改最下层的叶子,然后依次更新内节点。由于 Topology Tree 的高度为 O(log (m / z)) ,所以每次操作的复杂度为 O(m/z log (m/z))

考虑第三种情况。由于替换边的本质是重新维护块,而需要维护的块的个数是常数个,而且要构造常数个块的 Topology Tree ,所以复杂度是 O(m/z log (m/z) + z)

考虑第四种情况。这一步就可以通过维护的 Topology Tree 来加快速度。不妨设这条树边连接的是 x 和 y 。如果 x 和 y 在同一个块中,我们需要把这个块分裂成两个,这也可以通过改变常数个块来实现。在前一种算法中,我们要 O(m2/z2) 地枚举块对,现在我们只要枚举一个块,在这个块对应的 Topology Tree 中把 x-y 这条边删去,这样会产生两个 Topology Tree ,选择不包含这个块的 Topology Tree ,用维护的子树最小权的边即可更新答案。第一步的复杂度是 O(m/z log (m/z) + z) ,第二步的复杂度为 O(m/z log (m/z)) ,总时间复杂度为 O(m/z log (m/z) + z)

均衡一下,令 z = sqrt(m log m) 可以得到整个算法 per update 的时间复杂度为 O(sqrt(m log n)) 。真是太令人(理性)愉悦了~

O(sqrt(m)) per update

在上一种做法中,我们建立了 O(m / z) 棵 Topology Tree ,而这若干棵树的形态完全一样。于是我们可以考虑建立一棵“二维 Topology Tree ”来继续优化。

然后啪啦啪啦优化就是 O(sqrt(m)) 了 = =|| (具体过程正在看……)

\(O(\sqrt{n})\)