并查集的介绍.docVIP

并查集 在一些问题中，我们需要划分ｎ个不同的元素成若干组，每一组的元素构成一个集合。这种问题的一个解决办法是，在开始时，让每个元素自成一个单元集合，然后按一定顺序将属于同一组的元素所在的集合合并。期间要反复用到查找一个元素属于哪一个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-find sets)。 【知识准备】 等价关系：如果集合S中的关系R是自反的，对称的，传递的，则称他为一个等价关系。 ——自反：x＝x； ——对称：若x＝y，则y＝x； ——传递：若x＝y、y＝z，则x＝z。 要求：x、y、z必须要同一个子集中。 等价类：如果R是集合S的等价关系。对于任何x∈S，由[x]R＝{y|y∈S and xRy}给出的集合[x]R称为由x∈S生成的一个R的等价类。 若R是集合S上的一个等价关系，则由这个等价关系可产生这个集合的唯一划分。即可以按R将S划分为若干不相交的子集S1，S2，S3，S4，……，他们的并集为S，则这些子集Si称为S的R等价类。 划分等价类的问题的提法是：要求对S作出符合某些等价性条件的等价类的划分，已知集合S及一系列的形如“x等价于y”的具体条件，要求给出S的等价类的划分，符合所列等价性的条件。（我们上面提到的联系，即可认为是一个等价关系，我们就是要将集合S划分成n个联系的子集，然后再判断x，y是否在一个联系子集中。） 【并查集的实现】 它的数学模型是若干不相交的动态集合的集合S＝｛A,B,C,…｝，它支持以下运算： Initial(a,x)：构造以取名为A的集合，它只包括一个元素x; Merge(a,b):将集合A和集合B合并； 3. Find(x):找出元素x所在的集合。 实现方法一： 根据并查集的定义和应用我们不难想出一个并查集的最简单的实现方法，即开一个长度为n的一维数组来记录每个元素所属的集合。这样find和initial过程的实现都十分简单，而merge的实现过程也不难。实现如下： procedure merge(a,b:integer); var I:integer; begin for I:=1 to n do if c[I]=b then c[I]:=a; end; 上述3种运算的时间复杂度很容易分析，initial和find需要O（1）的时间，而merge需要O（n）的时间。 并查集的树实现： 实现并查集的另一种方式是利用树。我们可以把每一个集合用一棵树表示，集合中的每一个元素都存放在一个树的结点中。树的每一个结点都存放着一个指向其父亲的指针。此外，还需要两个映射。一个是集合中的元素到存放该元素的元素名的树结点的映射，另一个是集合的名字到该集合的树的树根的映射。如图： 1 2 3 4 这样完成initial和merge的时间复杂度为O（1），完成find的时间复杂度为O（m）,m为一棵树的高度。 容易看出，在最坏的情况下，树有可能退化成一条链（即m=n）,这时，完成find的时间复杂度为O(n),较先前没有什么改进。于是我们作一个简单改进，就是在每次的合并过程中将小树合并到大树中去，这样每次find过程只需要O(logn)的时间。 路径压缩： 加速并查集运算的另一个方法是路径压缩。 先看一个例子： 图中的两棵树表示同一个集合，而右边的树的高度远远小于左图树的高度。如果把左图情况全部转化为右图的情况可以大大降低时间复杂度。 路径压缩的具体方法如下：首先initail和merge过程不变。在执行find的过程中，我们实际上是走一条从一个节点到他所在的树的树根的路径。路径压缩就是要把这条路上的所有节点都改为树根的儿子。实现路径压缩的最简单的方法就是在这条路上走两次，第一次找到树根，第二次将路上的所有节点的父节点改为树根。如图一在执行了find(7)的过程后得到图二。 图二 图一 路径压缩的方法并不影响initial和merge,它们的时间仍为O(1),而在将小树