一分钟说清楚并查集

栏目: 数据库 · 发布时间: 6年前

内容简介:分离集合(disjoint set)是一种经典的数据结构,它有三类操作:它非常适合用来解决集合合并与查找的问题,也常称为并查集。

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

  • Make-set(a):生成包含一个元素a的集合S;
  • Union(X, Y):合并两个集合X和Y;
  • Find-set(a):查找元素a所在集合S,即通过元素找集合句柄;

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

一分钟说清楚并查集

一、并查集的链表实现

一分钟说清楚并查集

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

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

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

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

假设有集合:

S1={7,3,1,4} 
S2={1,6} 

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

一分钟说清楚并查集

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

合并完的效果是:

一分钟说清楚并查集

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

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

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

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

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

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

二、并查集的有根树实现

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

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

element{ 
         int data; 
         element* left; 
         element* right; 
} 

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

一分钟说清楚并查集

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

element{ 
         int data; 
         element* parent; 
} 

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

假设有集合:

S1={7,3,1,4} 
S2={1,6} 

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

一分钟说清楚并查集

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

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

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

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

一分钟说清楚并查集

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

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

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

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

一分钟说清楚并查集

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

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

一分钟说清楚并查集

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

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

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

结论

通过链表实现并查集:

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

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

通过有根树实现并查集:

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

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

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

【本文为51CTO专栏作者“58沈剑”原创稿件,转载请联系原作者】

一分钟说清楚并查集

戳这里,看该作者更多好文


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

大转换

大转换

尼古拉斯·卡尔 / 闫鲜宁、张付国 / 中信 / 2016-2 / 49

1、我们这个时代最清醒的思考者之一尼古拉斯·卡尔继《浅薄》《玻璃笼子》之后又一重磅力作。 2、在这部跨越历史、经济和技术领域的著作中,作者从廉价的电力运营方式对社会变革的深刻影响延伸到互联网对我们生活的这个世界的重构性影响。 3、《快公司》《金融时报》《华尔街日报》联袂推荐 简介 早在2003年,尼古拉斯·卡尔先生发表在《哈佛商业评论》上的一篇文章——IT Doesn't ......一起来看看 《大转换》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具