并查集的实现与性能优化

并查集是用于处理不相交集合的合并及查询问题,主要操作为:创建集合、合并两个不相交集合、判断两个元素是否属于同一个集合。

其中,判断两个元素是否属于同一个集合,可以这样考虑:为每个集合选一个代表元素,从而“判断两个元素是否属于同一个集合”就变成了“判断两个元素所在集合的代表元素是否相同”。

基本操作用函数表示如下:

  • Make-Set(x): 创建仅含元素 x 的集合
  • Union(x, y): 合并代表元素分别为 x 和 y 的集合
  • Find(x): 返回 x 所在集合的代表元素

并查集的链表实现

我们可以将每一个集合用一个链表来存储。链表的第一个结点作为集合的代表元素,每个结点都有一个域,用于指向该代表元素。

集合{c, h, e},c为代表元素

集合{f, g},f为代表元素

并集{f, g, c, h, e},f为代表元素

我们看到,合并这两个集合时,集合{c, h, e}被连接到了集合{f, g}后面,紧接着集合{c, h, e}中的所有元素的将代表元素都由 c 改成了 f。

显然,进行集合的合并操作时,连接两个集合的代价为 O(1) 时间,因此合并操作的主要代价是代表元素的修改,该操作需要将被连接到后面的集合中的所有元素都修改一遍,时间复杂度就等于后面的集合的元素个数。

简单改进

可以想到,合并集合时,位于后面的集合的元素个数越少,时间复杂度也就越小,因此我们可以简单改进一下合并操作,将元素个数少的集合连接到元素个数多的集合后面。

那么,如何知道哪个集合的元素较少?

我们给每个链表表头添加一个域,用于记录链表的长度,即元素的个数。每次进行合并操作时,根据该域找到元素较少的集合,将其连接到另一个集合的后面,并更新合并后集合的元素个数。

各种操作的时间复杂度:

  • Make-Set(x): 创建仅含元素x的一个链表,O(1)
  • Union(x, y): 连接x和y两个链表,更新元素指向的代表元素,O(min{|Sx|, |Sy|})
  • Find(x): 返回x指向的代表元素,O(1)

并查集的森林实现

每个集合表示为一棵树,树根为代表元素。每个结点的指针指向其父结点,根结点指向自身。

集合{c, h, e}

集合{f, d}

并集{f, d, c, h, e}

合并上述两个集合时,我们直接将集合{c, h, e}的代表元素(也就是树的根结点)c的父指针修改为集合{f, d}的代表元素f,Union 操作的时间复杂度由链表实现中的O(min{|Sx|, |Sy|})直接降到了O(1)。

但另一方面,Find 操作的时间复杂度就增加了。链表实现的 Find 操作可以直接返回元素中存放的代表元素的指针,但森林实现中,我们需要通过当前结点的父指针不断地访问到根结点,复杂度为根结点到x结点的深度O(Tx)。

极端情况下,如果所有元素都在树的一条路径上,x为最末尾的叶子结点,那么查找x所在集合的代表元素的代价将是O(Tx) = O(n)。

因此,路径的长度是影响 Find 操作时间复杂度的主要因素。

各种操作的时间复杂度:

  • Make-Set(x): 创建仅含元素x的一棵树,O(1)
  • Union(x, y): 将x作为y的孩子,O(1)
  • Find(x): 从结点x沿父指针访问直到树根,O(Tx)

优化:Find时压缩路径

由于结点所在路径的长度会影响到 Find 操作的效率,因此我们可以在每次执行 Find(x) 操作时,将结点 x 及路径上所有结点的父指针都修改为根结点。这样一来,虽然本次 Find 操作的时间复杂度较高,但是树中的路径长度大幅降低,为后续 Find 操作节省了时间。例如,以后对 x 执行 Find 操作的时间复杂度就降到了O(1)。

压缩前:

压缩后:

优化:Union时按秩合并

在进行合并操作时,将元素少的集合,合并到元素多的集合中。

规则如下:

  • Make-Set(x)操作执行时定义结点x的秩为0
  • Find操作不改变结点的秩
  • Union(x, y)分两种情况修改结点的秩:
    • 若rank(x) = rank(y),则令x指向y,rank(y)增加1
    • 若rank(x) != rank(y),则令rank值小的指向rank值大的结点,并且rank(x)和rank(y)保持不变。

采用按秩合并的方式,可以保证树的高度相对较小,使得 Find 操作的时间复杂度降低到O(α(n)),当元素的数量级小于10的80次方时,α(n)小于等于4。也就是说,实际应用中,Find操作的时间复杂度为常数时间O(1)。

发表评论

电子邮件地址不会被公开。 必填项已用*标注