一分钟说清楚并查集

简介:

分离集合(disjoint set)是一种经典的数据结构,它有三类操作:

Make-set(a):生成包含一个元素a的集合S;

Union(X, Y):合并两个集合X和Y;

Find-set(a):查找元素a所在集合S,即通过元素找集合句柄;

它非常适合用来解决集合合并与查找的问题,也常称为并查集

一、并查集的链表实现

286efd0c9db8af98054f5b446610e7ae8a9a7661

如上图,并查集可以用链表来实现。

链表实现的并查集,Find-set(a)的时间复杂度是多少?

集合里的每个元素,都指向“集合的句柄”,这样可以使得“查找元素a所在集合S”,即Find-set(a)操作在O(1)的时间内完成

链表实现的并查集,Union(X, Y)的时间复杂度是多少?

假设有集合:

S1={7,3,1,4}

S2={1,6}

合并S1和S2两个集合,需要做两件事情:

93cc9e6e45ffb95bf562e353b83be7d1ec8b532e

(1) 第一个集合的尾元素,链向第二个集合的头元素(蓝线1);

(2) 第二个集合的所有元素,指向第一个集合的句柄(蓝线2,3);

合并完的效果是:

f4bbc176fdb9e4bb506c6c7857c5a40398381eee

变成了一个更大的集合S1。

集合合并时,将短的链表,往长的链表上接,这样变动的元素更少,这个优化叫做“加权合并”。

画外音:实现的过程中,集合句柄要存储元素个数,头元素,尾元素等属性,以方便上述操作进行。

假设每个集合的平均元素个数是nUnion(X, Y)操作的时间复杂度是O(n)

能不能Find-set(a)与Union(X, Y)都在O(1)的时间内完成呢?

可以,这就引发了并查集的第二种实现方法。

二、并查集的有根树实现

什么是有根树,和普通的树有什么不同?

常用的set,就是用普通的二叉树实现的,其元素的数据结构是:

element{

         int data;

         element* left;

         element* right;

}

通过左指针与右指针,父亲节点指向儿子节点。

774565a5632301ff60965217bf7577356ccb0a66

而有根树,其元素的数据结构是:

element{

         int data;

         element* parent;

}

通过儿子节点,指向父亲节点。

假设有集合:

S1={7,3,1,4}

S2={1,6}

通过如果通过有根树表示,可能是这样的:

eff0cecbb85530f72845f248aad462eb194de963

所有的元素,都通过parent指针指向集合句柄,所有元素的Find-set(a)的时间复杂度也是O(1)。

画外音:假设集合的首个元素,代表集合句柄。

有根树实现的并查集,Union(X, Y)的过程如何?时间复杂度是多少?

通过有根树实现并查集,集合合并时,直接将一个集合句柄,指向另一个集合即可。

59fe76971d0fa2f49c3219d1ab26f29a5d50fd11

如上图所示,S2的句柄,指向S1的句柄,集合合并完成:S2消亡,S1变为了更大的集合。

容易知道,集合合并的时间复杂度为O(1)

会发现,集合合并之后,有根树的高度变高了,与“加权合并”的优化思路类似,总是把节点数少的有根树,指向节点数多的有根树(更确切的说,是高度矮的树,指向高度高的树),这个优化叫做“按秩合并”。

新的问题来了,集合合并之后,不是所有元素的Find-set(a)操作都是O(1)了,怎么办?

5b220ab7bd6df8ba6753cf73d56f3f80f730f212

如图S1与S2合并后的新S1,首次“通过元素6来找新S1的句柄”,不能在O(1)的时间内完成了,需要两次操作。

但为了让未来“通过元素6来找新S1的句柄”的操作能够在O(1)的时间内完成,在首次进行Find-set(“6”)时,就要将元素6“寻根”路径上的所有元素,都指向集合句柄,如下图。

ad81540e65810739e69e50122dc19bea8e7c13bb

某个元素如果不直接指向集合句柄,首次Find-set(a)操作的过程中,会将该路径上的所有元素都直接指向句柄,这个优化叫做“路径压缩”。

画外音:路径上的元素第二次执行Find-set(a)时,时间复杂度就是O(1)了。

实施“路径压缩”优化之后,Find-set的平均时间复杂度仍是O(1)

结论

通过链表实现并查集:

 ●  Find-set的时间复杂度,是 O(1) 常数时间
 ●  Union的时间复杂度,是集合平均元素个数,即 线性时间

画外音:别忘了“加权合并”优化。

通过有根树实现并查集:

 ●  Union的时间复杂度,是 O(1) 常数时间
 ●  Find-set的时间复杂度,通过“按秩合并”与“路径压缩”优化后,平均时间复杂度 也是O(1)

使用并查集,非常适合解决“微信群覆盖”问题。

思路比结论重要,有收获就是好的。


原文发布时间为:2018-11-20

本文作者:58沈剑 

本文来自云栖社区合作伙伴“架构师之路”,了解相关信息可以关注“架构师之路”。

相关文章
|
14天前
|
算法
并查集,路径压缩
并查集,路径压缩
16 0
|
14天前
并查集。。
并查集。。
19 0
|
6月前
|
C++
并查集及其应用
并查集及其应用
40 0
|
14天前
|
算法 测试技术
并查集算法
并查集算法
|
14天前
|
机器学习/深度学习
并查集(UnionFind)总结
并查集(UnionFind)总结
31 0
|
8月前
|
算法
并查集模板题
并查集模板题
29 0
|
11月前
|
存储 算法 iOS开发
并查集详解及应用
并查集详解及应用
3815 0

热门文章

最新文章