一分钟说清楚并查集

  1. 云栖社区>
  2. 阿里云MVP>
  3. 博客>
  4. 正文

一分钟说清楚并查集

初商 2019-08-08 23:25:59 浏览180
展开阅读全文

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

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

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

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

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

一、并查集的链表实现

image.png

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

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

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

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

假设有集合:

S1={7,3,1,4}

S2={1,6}

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

image.png

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

网友评论

登录后评论
0/500
评论
初商
+ 关注
所属云栖号: 阿里云MVP