Mengzelev's Blog

算法导论学习笔记-用于不相交集合的数据结构

Word count: 607 / Reading time: 2 min
2018/10/06 Share

不相交集合的操作

一个不相交集合数据结构维护了一个不相交动态集的集合
每个集合都有一个代表标识,它是该集合的某个成员

我们希望集合支持以下三个操作:

应用:确定无向图的连通分量




算法就是将连通的顶点全部合并到同一个集合中。

不相交集合的链表表示

每个集合可以用一个自己的链表来表示
链表中对象可以以任意次序出现

每个链表组成为:

  • head– 指向表的第一个对象(代表元)
  • tail– 指向表的最后一个对象

链表中每个对象的组成为:

  • 关键字key
  • 指向head的指针prev
  • 指向后一个对象的指针next

时间复杂度:
MAKE-SET O(1)
FIND-SET O(1)
UNION(简单实现) $\Theta(n^2)$ 【摊还分析】

简单加权合并启发式策略

策略是,每次合并时都将较小的链表挂到较大的链表上,需要多维护一个链表长度的属性。

证明的核心在于每个对象的指针在所有的UNION操作中最多被更新$\lceil\lg n\rceil$次,因此所有UNION操作中被更新的对象的指针总数为$O(n\lg n)$。加上MAKE-SETFIND-SEt的O(m)。

不相交集合森林

使用有根树来表示集合。
每棵树表示一个集合,树的根结点是该集合的代表元。
执行UNION操作时将两棵树的树根合并。
实现时可以用到两种改进运行时间的启发式策略。

按秩合并

类似链表的加权合并启发式策略
为了易于分析,对于每个结点,维护一个,表示该结点高度的一个上界。
x.rank代表x的高度的一个上界,高度即从x到某一后代叶结点的最长简单路径上边的数目
UNION操作中

  • 如果根的秩不同,则让较大秩的根成为较小秩的根的父结点,但秩本身保持不变
  • 如果根的秩相同,则任意选择两个中的一个作为父结点,并使它的秩+1

路径压缩

FIND-SET操作中是查找路径中的每个结点直接指向根,不改变任何结点的秩。

伪代码





CATALOG
  1. 1. 不相交集合的操作
    1. 1.1. 应用:确定无向图的连通分量
  2. 2. 不相交集合的链表表示
    1. 2.1. 简单加权合并启发式策略
  3. 3. 不相交集合森林
    1. 3.1. 按秩合并
    2. 3.2. 路径压缩
    3. 3.3. 伪代码