「进行中」Dynamic Minimum Spanning Tree

Posted on 2013-03-25 In CS/Math Disqus: Word count in article: 1.8k Reading time ≈ 7 mins.

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(m^2/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})\)