《Dynamic Connectivity》研究报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“dynamic365crm手册”。
2005年信息学国家集训队作业
安徽 周源
《Dynamic Connectivity》研究报告
安徽 周源
摘要及问题的提出
2005年信息学冬令营的考试中有一题dface，是一道主要关于图的连通性维护的试题，然而由于在那一题中的图由一些特殊性，因此可以提出一些比较简单的non-trivial的算法。不过是否对于任意图，都有一个高效的算法或数据结构可以动态维护其连通性呢？我对此非常感兴趣，查阅了不少资料，终于找到了这个新近才被提出来的算法：
要求设计一种数据结构，可以维护一个N个点的无向图，支持插入、删除、以及查询某两个点是否在一个连通分量中这3种操作。
每次更新维护需要花费O(log2N)的时间，而查询操作则需要花费O(logN)的时间。
算法描述
1.基本数据结构：欧拉回路树（Euler Tour Tree）
欧拉回路树可以维护一个N个点的森林，支持插入（保证插入边后不会出现环）、删除、以及查询某些点是否在同一颗树中。
这个数据结构的各种操作，可以在O(logN)的时间内完成（加入一些优化后，询问时间复杂度可以降为O(logNloglogN），不过这并没有太多的实际意义）。
一个ET-Tree，一般可以用标准平衡二叉树(standard balanced binary tree)来实现：对于森林中的每一棵树，用一个二叉树来存储这棵树的欧拉回路（将每一条无向边重复成两条有向边，就一定存在一个欧拉回路）。
将森林中两棵树合并，就是将这两棵树对应的欧拉回路——即两个环相接。考虑到是环而不是链，最多是用两次平衡树的连接操作（concatenation）就可以实现了。
同样，删去树中的某条边，就是将一棵树分裂为两棵，即分裂对应的欧拉回路环。使用最多两次平衡树的分裂操作（split）即可。
询问两个点是否在同一连通分量中，等价于询问和这两个点连接的边（任取一条）是否在同一颗平衡树中，判断它们的平衡树根是否相同即可。
综上所述，每一条必要的操作，都可以在O(logN)时间内完成。
2.交换边（Replacement Edge）
当我们期望设计功能更强大的数据结构来维护任意图而不是树的时候，情况就会变得复2005年信息学国家集训队作业
安徽 周源
杂起来。我们可以设想这样一种方法：利用欧拉回路树以及其它的一些技巧维护一个“当前图的生成树林”。
在这个方法中，加入一条边是很容易的：只需要判断待加入边是否连接这两颗不同的树，如果不是则可以什么也不做，否则将这两棵树合并起来即可。使用欧拉回路树，可以在O(logN)的时间内做到。
在维护森林时，删去一条边，则边两端的点一定不会连通；而在维护任意图的时候，情况复杂多了：如果需要删除的边，不在我们正在维护的生成树林中，则仅仅从集合中删去这条边就可以了；而如果这正是生成树林中的一条边，若将它从树中删去，则这棵树会分裂成为两部分。然而先前插入的某条不在树上的边却又可能将这两部分连接起来。因此，算法的中间就在于，如何寻找这样一条交换边。
自然的想法是检测所有的非树边（下文中的非树边，non-tree edges即表示先前插入的，却不是生成树林上的边），然而这样的耗费太大了。
3.算法轮廓
我们的算法将正在维护的图中边的集合分为O(logN)层(level)：第0层，第1层，第2层，…，第logN层。每一条边都属于且仅属于某一层。
设Ei表示第i层中，边的集合。那么对于每一层，我们维护一个生成树林Fi，Fi是第i以及更高层的一个生成树林：UjiEi。且Fi Fi-1(i>0)。因此F0就是整个图的生成树林。
所以可以说，Fi就是F0中第i层边的集合。同样可以看出，我们的生成树林中第i层的边将第(i+1)或以上层的边形成的连通分量连接起来。
这样一来，可以看出，如果删除了某一条第i层的树上的边，则其对应的交换边所在的层数一定不会高于i。
我们的动态算法，即维护这样一个图G的生成树林F。F中的边将被称为树上边（tree-edges）。同样，如上文所述，将每一条边e与某一层l(e)≤L=log2N关联，即e属于第l(e)层。且对于每一层i，如上文定义Fi：F = F0 F1 F2 … FL。并需要保证下列性质成立：
a)对于每一层而言，Fi是该层以及该层以上所有边的一颗尽量大的生成树，即如果存在边(u, v)是非树边，那么u, v一定在Fl(u, v)中被连接。
b)Fi中最大的连通分量的节点个数，不得超过[
n2i]，即最大的非空层为logN。
在算法的初始时刻，所有的边都位于第0层，这样满足上述的所有条件。那么我们可以较为细致的描述算法如何实现各种操作：
Insert(e)：将新加入的边放入第0层：E0，如果这条边连接了F0的两个不同的连通分量，则将这条边加入F0。
Delete(e)：如果e是一条非树边，则仅仅在El(e)中将其删去即可。否则若e是一条树上边，那么将其删去，并寻找一条交换边来重新连接被分开的两部分。由于交换边所在的层数一定不大于l(e)，因此我们可以调用Replace(e, l(e))来寻找交换边。
Replace(e(v, w), i)：假设在第i层以上都不存在e的可交换边，那么我们这个过程试图在level ≤ i的集合中，寻找一条层数尽可能高的交换边。
假设Tv和Tw是在Fi中删除e以后包含点u和v的两个连通分量。不是一般性的假设|Tv|≤|Tw|，则在删除之前，T = Tv ∪ {e} ∪ Tw是第i层的一棵树，它至少含有|Tv|两倍多的节2005年信息学国家集训队作业
安徽 周源
点。由b)性质，T最多有[
n2i]个节点，因此，Tv最多有[
n2i1]个节点。所以我们可以将Tv中所有第i层的边移入第(i+1)层，而不触犯任何性质：即让Tv成为第(i+1)层的一棵树。
这样，我们枚举第i层的所有一端端点在Tv的非树边f，依次判断他们是否可以成为一条交换边。
如果f不能连接Tv和Tw，则根据性质a)，f的两个端点一定都属于Tv，则将其改为第(i+1)层的边而不会影响每一条性质的成立。而这次增加，则可以作为检测f需要的时间费用。
如果f连接Tv和Tw，则f就是一条交换边，将其插入树中，我们的检测过程结束。如果将所有第i层的与Tv连接的非树边检测完毕而仍为找到交换边，则继续调用Replace(e(v, w), i-1)，若i=0，则过程结束，我们可以断定整个图中没有交换边。
4.平摊复杂度分析
上述的每一种基本操作，利用欧拉回路树均可以在O(logN)时间内实现。而纵观整个算法，如果一条边被插入，那么它被直接加入第0层，需要O(logN)的时间，然而它的层数可能会被提升O(logN)次，每次需要O(logN)的代价，因此其平摊时间复杂度为O(log2N)。
删除一条非树边，需要O(logN)的时间，当一条树上边被删除时，我们需要将F（jj≤l(e)）中的这条边都删除，需要O(log2N)的时间，接着调用Replace过程：最多调用O(logN)次，每次都需要O(logN)的时间（除去被平摊为插入的时间代价），这一部分的时间复杂度也是2O(logN)。
至于询问操作，我们只需要询问两个被询问点在F0中是否属于同一个连通分量，在欧拉回路树的描述中曾经说过，这一步的时间复杂度为O(logN)。
小结及展望
这个算法的理论时间效率是比较高的，若是应用在冬令营考试的dface上，可能会在时限的1/5甚至1/10的时间内出解。然而这个算法实现起来十分复杂，我曾经试图写过这个算法的程序，然而在写了600多行后发现有很多细节问题没有考虑周全而不得不宣告放弃。另一个方面，由于实现起来复杂，如何降低其不必要的系数也是我所关心的问题。
希望有高手能够将这个理论上非常优秀的算法变成一个真正优秀的程序！
