|
- UID
- 1029342
- 性别
- 男
|
简介：不相交集类是将一些元素合并为不相交的各个集合。在同一个集合中的元素两两等价，不同集合中的元素不等价。
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； ?
1
| vector<int> s;//存放每个元素的根节点或父节点</int>
|
对元素x的一次find(x)操作通过返回包含x的树的根而完成。合并操作union(root1, root2)，将一棵树的父节点链接到另一棵树的根节点合并两棵树。下面是具体的例子：初始化元素集合：0,1,2,3,4,5,6,7 合并操作union(4,5)，将一棵树的父节点链接到另一棵树的根节点合并两棵树。  合并操作union(6，7)，将一棵树的父节点链接到另一棵树的根节点合并两棵树。   4.灵巧求并算法上面不相交集类中的合并函数是想当随意的，它通过使第二棵树成为第一棵树的子树而完成合并。 第一种改进方法：对其进行简单的改进是借助任意的方法打破现在的随意性，使得总是较小的树成为较大的树的子树。将这种方法称为按大小求并。 如果不是按大小求并，那么随着合并的进行，某些集合树的深度会增加太多（大于logN)，这意味这find操作的执行时间为O(logN)。为了实现按大小合并的方法，需要记住每棵树的大小，可以让每个根元素包含它的树的大小的负值。合并的时候首先检查树的大小，将较小的树成为较大树的子树，新的树的大小为两棵树大小的和。 按大小合并的例子步骤：    |
|
