数据结构
计算机领域本科教育教学改革试点
工作计划（“101计划”）研究成果
101
不相交集
第9章
陈键飞
清华大学
9.1 问题引入
9.2 等价关系、等价类和不相交集
9.3 不相交集的存储实现
9.4 不相交集的基本运算实现
9.5 不相交集的应用
9.6 拓展延伸
9.7 应用场景
9.1问题引入：Kruskal算法的高效实现
9.1问题引入
数据结构
9.1问题引入：Kruskal算法的高效实现
9.1问题引入
数据结构
9.1问题引入：Kruskal算法的高效实现
9.1问题引入
数据结构
注意：只需要查询顶点之间是否连通，不关心它们具体通过哪条路径连通
此外，只需要支持加边操作，而不需要支持删边操作。
这种情况下，与其完整地维护无向图的结构，不如直接维护连通分量构成的集合
每个连通分量用其中顶点的集合表示。
连通性查询问题变成了维护若干不相交的集合，并动态地合并、查找的问题。
9.1问题引入：Kruskal算法的高效实现
9.1问题引入
数据结构
9.2等价关系、等价类和不相交集
9.2等价关系、等价类和不相交集
数据结构
不相交集与数学中等价关系、等价类的概念密切相关
元素之间的等价关系自然地定义了若干不相交集的集合
因此，不相交集常常用于处理等价性查询的问题
例如，两个顶点在同一连通分量中就可以看做一种等价性
9.2等价关系、等价类和不相交集
9.2等价关系、等价类和不相交集
数据结构
9.2等价关系、等价类和不相交集
9.2等价关系、等价类和不相交集
数据结构
例9.1.不同问题中的等价关系：
9.2等价关系、等价类和不相交集
9.2等价关系、等价类和不相交集
数据结构
对集合中的任意元素，称所有与其等价的元素为一个等价类：
等价关系把集合划分成若干个不相交的等价类，每个等价类中的元素互相等价。
称所有等价类构成的集合为一个商集。
商集是一系列集合，这些集合彼此不相交，并且其并集是全集X。这与不相交集的概念恰好对应。
9.2等价关系、等价类和不相交集
9.2等价关系、等价类和不相交集
数据结构
9.2等价关系、等价类和不相交集
9.2等价关系、等价类和不相交集
数据结构
不相交集可以用于等价性的动态查询。
等价性的查询在计算机科学中有广泛应用。例如，在编译器的设计中，用于判断符号地址的等价性。
9.3不相交集的存储实现
9.3不相交集的存储实现
数据结构
不相交集数据结构定义：
例：考虑集合X={1,2,3,4,5,6,7,8}。
合法的划分：{{1,2,3,4,5},{6,7},{8}}或{{1}{2},{3},{4},{5},{6},{7},{8}}；
以下不是集合X的划分:{{1,2,3,4,5},{6,7}}和{{1,2,3},{3,4,5},{5,6,7,8}}。
9.3不相交集的存储实现
9.3不相交集的存储实现
数据结构
不相交集的数据结构需要动态处理集合的合并和查询操作，其ADT定义如下：
9.3不相交集的存储实现
9.3不相交集的存储实现
数据结构
9.4不相交集的基本运算实现
9.4不相交集的基本运算实现
数据结构
9.4不相交集的基本运算实现
9.4不相交集的基本运算实现
数据结构
9.4不相交集的基本运算实现
9.4不相交集的基本运算实现
数据结构
9.4.1按秩合并
9.4不相交集的基本运算实现
数据结构
9.4.1按秩合并
9.4不相交集的基本运算实现
数据结构
采取按秩合并策略后，InitSet和Union操作的实现调整为算法9-4、算法9-5：
9.4.1按秩合并
9.4不相交集的基本运算实现
数据结构
9.4.1按秩合并
9.4不相交集的基本运算实现
数据结构
9.4.2路径压缩
9.4不相交集的基本运算实现
数据结构
9.4.2路径压缩
9.4不相交集的基本运算实现
数据结构
9.4.2路径压缩
9.4不相交集的基本运算实现
数据结构
下图演示了同时采用按秩合并和路径压缩策略时，8个元素构成的不相交集的合并过程。
采用了按秩合并和路径压缩的
不相交集运行示例
9.4.2路径压缩
9.4不相交集的基本运算实现
数据结构
9.4.2路径压缩
9.4不相交集的基本运算实现
数据结构
9.4.3时间复杂度分析?
9.4不相交集的基本运算实现
数据结构
9.4.3时间复杂度分析?
9.4不相交集的基本运算实现
数据结构