并查集

背景:如果我们需要将元素划分到若干不相交的子集中,使用并查集可以快速确定某两个元素是否位于同一个子集。

并查集是一种数据结构,除了Union-Find Set,又叫做Disjoint-Set。更确切的说,它主要包含了两种操作:Find和Union。具体信息可以见维基百科:《Disjoint-set data structure 》

并查集主要包含两个操作:

Find(x):返回元素位于那个划分的子集合内。

Union(x, y):将x, y两个集合中的元素合并为一个集合。

其实还有一个操作,Make_Set(x):初始化x元素,让他属于独立的集合(它子集)。

并查集的最子出思想:为每一个集合x创建一个链表,链表的表头被选为“代表元”(root)。代表元的parent指向子集,而链表的其他元素直接或间接指向root(间接是由union操作导致的)。

因此,查找的时候,我们将递归查找,直到到达代表元root。

下面是一个最naive版本的并查集实现:

上述naive的Find的时间复杂度是O(logn),合并的复杂度是O(1)。

上述并查集的实现有很多可以优化的空间。

最简单的是路径压缩(Path Compression)。实际上,在Find是一个递归的过程,而这之中很多结点的parent都是被多次、反复查找过的,我们可以用类似记忆化搜索的方法,“缓存”这些parent,让他们在计算过一次后,直接指向最终的“代表元”。这样,Find的实践复杂度会下降为O(a(n)),其中a(n)是Ackermann的反函数。对于大部分可以观察到的n,其值都是5以内。所以时间复杂度非常低!

另外一个优化是合并(Union by rank)。这主要是为了解决合并的平衡问题。即,我们总是应该把较小(层少)的数合并到大的树上。

为此,我们给每个元素加上一个秩rank,代码如下:

 

Leave a Reply

Your email address will not be published.