解决等价问题
等价关系可以表示为布尔型的二维数组,则可以在 内测试等价性,但是关系给出的时候可能是隐式的,需要推导才能知道
不相交集合的操作
- find:找出特定元素属于哪个等价类
- union:把两个等价类合并
并不关心元素的值,只关心在哪个集合中,所以可以简单将这些元素顺序编号
在查找操作时候,不关心等价类名字,只需要知道 a 和 b 在同一个集合中返回的结果是相同的就行
存储方式
- 线性表存储:存每个元素所在的等价类名字,find 操作是 的,union 是
- 树:union 是 ,find 是 (后面采用这种方式)
等价类的名字为根节点的名字,数组中保存的值是索引 i 对应的父节点
优化树的平衡性:如果是树根,可以存一个负的树的规模,小的规模的树并入大的规模的树;或者存树的高度,高度小的并入高度大的
路径压缩:在 find 的时候,往树根寻找的时候顺便把路径上的每一个节点都改成自己的父节点(和规模存储兼容)
应用: 生成迷宫问题