算法设计与分析——并查集（Union-find Disjoint Sets）_并查集链表表示

分类目录：《算法设计与分析》总目录

---

一些应用涉及将$n$个不同的元素分成一组不相交的集合。这些应用经常需要进行两种特别的操作：

• 寻找包含给定元素的唯一集合
• 合并两个集合

一个不相交集合数据结构维护了一个不相交动态集的集合 S = { S 1 , S 2 , ⋯   , S k } \mathbb{S}=\{S_1, S_2, \cdots, S_k\} S={S1​,S2​,⋯,Sk​}。我们用一个代表来标识每个集合，它是这个集合的某个成员。在一些应用中，我们不关心哪个成员被用来作为代表，仅仅关心的是2次查询动态集合的代表中，如果这些查询没有修改动态集合，则这两次查询应该得到相同的答案。其他一些应用可能会需要一个预先说明的规则来选择代表，比如选择这个集合中最小的成员。

用一个对象表示一个集合的每个元素。设$x$表示一个对象，我们希望支持以下三个操作：

• make_set(x)：建立一个新的集合，它的唯一成员（因而为代表）是$x$。因为各个集合是不相交的，故$x$不会出现在别的某个集合中。
• union(x, y)：将包含$x$和$y$的两个动态集合合并成一个新的集合，即这两个集合的并集。假定在操作之前这两个集合是不相交的。虽然union(x, y)的很多实现中特别地选择$S_x$或$S_y$的代表作为新的代表，然而结果集的代表可以是$S_x\cup S_y$的任何成员。由于我们要求各个集合不相交，故要“消除”原有的集合$S_x$和$S_y$，即把它们从$\mathbb{S}$中删除。实际上，我们经常把其中一个集合的元素并人另一个集合中，来代替删除操作。
• find_set(x)：返回一个指针，这个指针指向包含$x$的集合的代表。

我们使用两个参数来分析不相交集合数据结构的运行时间：一个参数是$n$，表示make_set(x)操作的次数；另一个是$m$，表示make_set(x)、union(x, y)和find_set(x)操作的总次数。

因为各个集合是不相交的，所以每个union(x, y)操作减少一个集合。因此，$n-1$次union(x, y)操作后，只有一个集合留下来。也就是说，union(x, y)操作的次数至多是$n-1$。也要注意到，由于make_set(x)操作被包含在总操作次数$m$中，因此有$m\ge n$。这里我们假设$n$个make_set(x)操作总是最先执行的$n$个操作。

并查集的链表表示

下图(a)给出了一个实现不相交集数据结构的简单方法：每个集合用一个自己的链表来表示。每个集合的对象包含head属性和tail属性，head属性指向表的第一个对象，tail属性指向表的最后一个对象。链表中的每个对象都包含一个集合成员、一个指向链表中下一个对象的指针和一个指回到集合对象的指针。在每个链表中，对象可以以任意的次序出现。代表是链表中第一个对象的集合成员。

用这种链表表示，make_set(x)操作和find_set(x)操作是非常方便的，只需$O(1)$的时间。

要执行make_set(x)操作，我们需要创建一个只有$x$对象的新的链表。对于find_set(x)，仅沿着$x$对象的返回指针返回到集合对象，然后返回head指向对象的成员。例如，在图(a)中，find_set(g)的调用将返回f。

在使用链表集合表示的实现中，union(x, y)操作的最简单实现明显比make_set(x)操作或find_set(x)操作花费的时间多。如图(b)所示，我们通过把$y$所在的链表拼接到$x$所在的链表实现了union(x, y)。$x$所在的链表的代表成为结果集的代表。利用$x$所在链表的tail指针，可以迅速地找到拼接$y$所在的链表的位置。因为$y$所在的链表的所有成员加入了$x$所在的链表中，此时可以删除$y$所在的链表的集合对象。遗憾的是，对于$y$所在链表的每个对象，我们必须更新指向集合对象的指针，这将花费的时间与$y$所在链表长度呈线性关系。

事实上，我们能轻松构建一个在$n$个对象上需要$\Theta (n^2)$时间的$m$个操作序列。假设有对象$x_1,x_2,\cdots ,x_n$，执行$n$个make_set(x)操作，后面跟着执行$n-1$个union(xj, xj)操作，因而有$m=2n-1$。执行$n$个make_set(x)操作需要$\Theta (n)$的时间。由于第$i$个union(xj, xj)操作更新$i$个对象，因此所有的$n-1$个union(xj, xj)操作更新的对象的总数为$\Theta (n^2)$。总的操作数为$2n-1$，这样每个操作平均需要$\Theta (n)$的时间。也就是说，一个操作的摊还时间为$\Theta (n)$。

在最坏情况下，上面给出的union(xj, xj)过程的每次调用平均需要$\Theta (n)$的时间，这是因为需要把一个较长的表拼接到一个较短的表上，此时必须对较长表的每个成员更新其指向集合对象的指针。现在换一种做法，假设每个表中还包含了表的长度以及拼接次序可以任意的话，我们总是把较短的表拼接到较长的表中。使用这种简单的加权合并启发式策略，如果两个集合都有$\Omega (n)$个成员，则单个的union(xj, xj)操作仍然需要$\Omega (n)$的时间。然而下面的证明表明，一个具有$m$个make_set(x)、union(x, y)和find_set(x)操作的序列（其中有n个是make_set(x)操作）需要耗费$O(m+n\log n)$的时间。

由于每个union(xj, xj)操作合并两个不相交集，因此总共至多执行$n-1$个union(xj, xj)操作。现在来确定由这些union(xj, xj)操作所花费时间的上界。我们先确定每个对象指向它的集合对象的指针被更新次数的上界。考虑某个对象$x$，我们知道每次$x$的指针被更新，$x$早先一定在一个规模较小的集合当中。因此第一次$x$的指针被更新时，结果集一定至少有2个成员。类似地，下次$x$的指针被更新时结果集一定至少有4个成员。一直继续下去，注意到对于任意的$k\le n$，在$x$的指针被更新$\rceil \log n\lceil$次后，结果集一定至少有$k$个成员。因为最大集合至多包含$n$个成员，故每个对象的指针在所有的union(xj, xj)操作中最多被更新$\rceil \log n\lceil$次。因此在所有的union(xj, xj)操作中被更新的对象的指针总数为$O(n\log n)$。当然，我们也必须考虑tail指针和表长度的更新，而它们在每个union(xj, xj)操作中只花费$O(1)$时间。所以总共花在union(xj, xj)操作的时间为$O(n\log n)$。整个$m$个操作的序列所需的时间很容易求出。每个make_set(x)操作和find_set(x)操作需要$O(1)$时间，它们的总数为$O(m)$。所以整个序列的总时间是$O(m+n\log n)$。

并查集的树和森林表示

在一个并查集更快的实现中，我们使用有根树来表示集合，树中每个结点包含一个成员，每棵树代表一个集合。在一个并查集森林中，每个成员仅指向它的父结点。每棵树的根包含集合的代表，并且是其自己的父结点。正如我们将要看到的那样，虽然使用这种表示的直接算法并不比使用链表表示的算法快，但通过引入两种启发式策略（“按秩合并”和“路径压缩”），我们能得到一个渐近最优的并查集结构。

我们执行以下三种不相交集合操作：make_set(x)操作简单地创建一棵只有一个结点的树，find_set(x)操作通过沿着指向父结点的指针找到树的根。这一通向根结点的简单路径上所访问的结点构成了查找路径。union(x, y)操作（如下图(b)所示）使得一棵树的根指向另外一棵树的根。

到目前为止，我们还没有对使用链表的实现做出改进。一个包含$n-1$个union(x, y)操作的序列可以构造出一棵恰好含有$n$个结点的线性链的树。然而，通过使用两种启发式策略，我们能获得一个几乎与总的操作数$m$呈线性关系的运行时间。

第一种启发式策略是按秩合并，它类似于链表表示中使用的加权合并启发式策略。显而易见的做法是，使具有较少结点的树的根指向具有较多结点的树的根。这里并不显式地记录每个结点为根的子树的大小，而是采用一种易于分析的方法。对于每个结点，维护一个秩，它表示该结点高度的一个上界。在使用按秩合并策略的union(x, y)操作中，我们可以让具有较小秩的根指向具有较大秩的根。

第二种启发式策略是路径压缩，也相当简单和高效。正如下图所示，在find_set(x)操作中，使用这种策略可以使查找路径中的每个结点直接指向根。路径压缩并不改变任何结点的秩。~

并查集的Python实现

class UnionFind(object):
    """并查集类"""
	def __init__(self, n):
        """长度为n的并查集（初始化方法一）"""
		"""每一个结点初始化为-1，列表的结点值为负数表示它自己就是根结点，可以用-n表示自己的子结点的数量"""
		
        self.uf = [-1 for i in range(n + 1)]    # 列表0位置空出
        self.sets_count = n                     # 判断并查集里共有几个集合, 初始化默认互相独立

"""	
	def __init__(self, n):
        """长度为n的并查集（初始化方法二）"""
	    """用列表的下标初始化对应位置的值，当一个并查集S[i] == i时则判断它自己就是根结点"""
	
        self.uf = [i for i in range(n + 1)]     # 列表0位置空出
        self.sets_count = n                     # 判断并查集里共有几个集合, 初始化默认互相独立
"""
		
	def find(self, p):
        """查找p的根结点(祖先)"""
		"""在规模很大的情况下，O(n)的查询时间复杂度是不被接受的，改进的方法就是路径压缩。路径压缩就是在查找根结点的过程中，顺便把子结点的父结点改成根结点，这样下次查询的效率只需要O(1)的时间复杂度就可以完成，大大提高了效率"""
        r = p                                   # 初始p
        while self.uf[p] > 0:
            p = self.uf[p]
        while r != p:                           # 路径压缩, 把搜索下来的结点祖先全指向根结点
            self.uf[r], r = p, self.uf[r]
        return p

    def union(self, p, q):
        """连通p,q 让q指向p"""
		"""直接右往左合并的缺点就是当右边的规模大于左边的规模时，在查找时，做路径压缩需要把右边所有的根结点更改为左边的根结点，所以合并的一种优化方式就是按规模合并，即把规模小的树往规模大的树上合并。其实还有一种按秩合并(树高度小的往高度大的合并而不改变树的整体高度)，但是这种方法不与路径压缩兼容，因为路径压缩直接改变了树的高度，所以这里选择按规模合并和路径压缩结合的方式优化并查集"""
        proot = self.find(p)
        qroot = self.find(q)
        if proot == qroot:
            return
        elif self.uf[proot] > self.uf[qroot]:   # 负数比较, 左边规模更小
            self.uf[qroot] += self.uf[proot]
            self.uf[proot] = qroot
        else:
            self.uf[proot] += self.uf[qroot]    # 规模相加
            self.uf[qroot] = proot
        self.sets_count -= 1                    # 连通后集合总数减一
 
    def is_connected(self, p, q):
        """判断pq是否已经连通"""
		return self.find(p) == self.find(q)     # 即判断两个结点是否是属于同一个祖先
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46