【数据结构与算法】【不相交集】定义和基本操作

不相交集是解决等价问题的一种有效的数据结构，之所以称之为有效是因为，这个数据结构简单（几行代码，一个简单数组就可以搞定），快速（每个操作基本上可以在常数平均时间内搞定）。

首先我们要明白什么叫做等价关系，而在这个之前要先有一个关系（relation）的定义

Relation：定义在数据集S上的关系R是指，对于属于数据集S中的每一对元素（a，b），a R b要么是真要么是假。如果a R b为真，就说a related b，即a与b相关。

等价关系也是一种关系（Relation），只不过是要满足一些约束条件

a） a R a，对于所有属于S的a

b） a R b 当且仅当 b R a

c） a R b 并且 b R a 意味着 a R c

动态等价性问题：

定义在非空集合S上的关系R，对于任意属于数据集S中的每一对元素（a，b），确定a R b是否为真，也就是说a与b是否有关系。

而对于a与b是否有关系，我们只需要证明a与b是否在同一个等价类集合中。

1）基本结构

Find操作：返回给定元素的集合的名字，也就是检查a，b是否在同一个等价类中。对于Find运算，最重要的是判断Find（a，S） == Find（b，S）是否成立。

Union操作：如果a，b不在一个等价类中，可以用Union操作把这连个等价类合并为一个等价类。

我们可以用tree结构来表示一个集合，root可以表示集合的名字。由于仅有上面的两个操作而没有顺序信息，因此我们可以将所有的元素用1-N编号，编号可以用hashing方法。

进一步可以发现对于这两个操作无法使其同时达到最优，也就是说当Find以常数最坏时间运行时，Union操作会很慢，同理颠倒过来。因此就有了2种实现方式。

a）使Find运行快

在数组中保存每个元素的等价类的名字，将所有等价类的元素放到一个链表中

b）使Union运行快

使用树来表示每一个集合，根节点表示集合的名字。数组元素P[i]表示元素i的父亲，若i为root，则P[i]=0。

对于Union操作，相当于把连个树合并，也就是指针的移动，如下图所示：