1.等价关系等价关系必须满足下面三个性质:
(1):自反性,对于集合S中的任意元素a,a R a;(R为定义的关系,比如R为<=, >=等等)
(2);对称性,a R b当且仅当b R a
(3):传递性,若a R b且b R c,则a R c 2.动态等价性问题集合S中元素a的等价类是集合S的一个子集,该等价类中包含所有与a有等价关系的元素。所以为确定a是否等价b,只需要验证a和b是否属于同一个等价类中。 find操作,它返回包含给定元素的等价类集合的名字。比如:find(a) == find(b),那么a和b处于同一个集合中。添加操作,如果想添加关系a ~ b,那么首先要判断a和b是否有关系(可以通过find操作验证它们是否在同一个等价类中)。如果a和b不在同一个等价类中,那么要使用求并操作union,这种操作将含有a和b的两个等价类合并为一个等价类。把这种算法称为不相交集合的求并/查找算法。该算法是动态的,因为在算法的执行过程中,集合可以通过union操作而发生改变。 解决动态等价性问题的方案有两种,第一种方案可以保证指令find能够以常数最坏情形运行时间执行,而另一种方案可以保证操作union能够以常数最坏情形运行时间执行。但是两个操作不能同时以常数最坏情形时间执行。 第一种方案:为使find操作快,可以在一个是数组中保存每个元素的等价类的名字。此时find就是简单的O(1)查找。设执union(a,b),并设a在等价类i中,b在等价类j中,此时我们扫描该数组,将所有的i都改变为j。union的时间复杂度为O(N); 第二种方案:将所有在同一个等价类中的元素放到一个链表中,更新的时候不用搜索整个数组。如果我们还要跟踪每个等价类的大小,并在执行union时将较小的等价类的名字改为较大的等价类的名字。 3.基本数据结构可以将每个元素都看作是一棵独立的树,每个集合的名字用树根表示,可以用一个数组就可以实现该思路。将所有的元素用一个数组表示,数组每个成员s表示元素i的父亲,如果i是根,那么s=-1; ?