首页 > 代码库 > 数据结构与算法分析（四）——不相交集
数据结构与算法分析（四）——不相交集
- 基本介绍
一个集合S，集合中一个元素a。a的等价类是S的一个子集，该子集包含所有与a有关系的元素。
等价类形成是对S的一个划分且S中的每一个成员恰好出现在一个等价类中。这样，判断a与b是否有关系，
只需要判断a与b是否在一个等价类中即可。
对于集合S划分，取任意两个等价类，Si与Sj，如果Si∩Sj = ∅，则称这些集合不相交。
对于不相交集，有两种操作，Union/Find操作。Find操作找包含给定元素的集合（等价类）名字。
Union把两个等价类合并成一个新的等价类。
- 数据结构：采用树来表示每一个集合（等价类），因为树上的元素都有一个共同的根。
Union(X, Y)，将X,Y合并成一个新的等价类，且X做为根。
Union(5,6)
Union(7,8)
Union(5,7)
这样的构造方法，最坏情况下可以构建一课高度为N-1的树，即Union(7,8), Union(6,7), Union(5,6)……
这使得Find操作在N-1次操作下才能找到树根，运行时间O（N）
将上述森林用数组表示，约定数组1-8个元素对应的值代表其父亲，例如元素8对应的值为7，表示其父亲为7。
而5对应的值为0，表示5本身就是树根。
这样找树根就是一个递归过程，如：Find(8), 父亲为7， 执行Find(7)，父亲为5，执行Find(5)，对应值为0，表示5为树根，递归结束，
这样即找到8所在等价类的树根为5。判断6,8是否有关系，即Find(8) == Find(6)是否成立。
1 typedef int SetType; 2 typedef int ElementType; 3 typedef int* DisjSet; 4 5 DisjSet Initialize(int Num) 6 { 7 DisjSet S = new SetType[Num + 1]; 8 9 for(int i = 0; i < Num + 1; i++) 10 S[i] = 0; 11 return S; 12 } 13 14 void Destroy(DisjSet S) 15 { 16 delete [] S; 17 } 18 19 void Union(DisjSet S, SetType root1, SetType root2) 20 { 21 S[root2] = root1; 22 } 23 24 SetType Find(DisjSet S, ElementType X) 25 { 26 if(S[X] <= 0) 27 return X; 28 else 29 return Find(S, S[X]); 30 } 31 32 int main() 33 { 34 int elementNum = 8; 35 DisjSet S = Initialize(elementNum); 36 37 Union(S, 5, 6); 38 Union(S, 7, 8); 39 Union(S, 5, 7); 40 41 cout << ( Find(S, 4) == Find(S, 5) )<< endl; 42 cout << ( Find(S, 6) == Find(S, 8) )<< endl; 43 44 Destroy(S); 45 system("pause"); 46 return 0; 47 }
- 优化Union
为了避免树的深度过大，可以每次让深度大的树做为新根，这样减少树深度增加速率。
那么就需要记住当前根的深度，而由于我们只采用了一个数组，所以，可以让根的值为负值，代表深度。
这样，根节点的值为-1，表示深度为-1。
对于上述情形，执行Union(4,5)。按照之前的Union操作，得到结果为：
优化后结果
对应优化后结果的数组如下：
1 void Union(DisjSet S, SetType root1, SetType root2) 2 { 3 if(S[root2] < S[root1]) 4 S[root1] = root2; 5 else 6 { 7 if(S[root1] == S[root2]) 8 S[root1]--; 9 S[root2] = root1; 10 } 11 }
- 路径压缩
对于比较深的树，Find操作还是比较耗时的，要一步一步递归直至树根。
改进思路：执行一次Find后，让该路径上，所有节点直接指向根，而不需要指向父亲，这样下一次查找的时候能够快速找到根，节约时间。
执行一次Find(8)操作。由于元素8所在树的树根为5，所以执行Find后，数组要变成。
这样，当进行下一次调用Find(8)的时候，能够快速找到8对应的树根。
1 SetType Find(DisjSet S, ElementType X) 2 { 3 if(S[X] <= 0) 4 return X; 5 else 6 return S[X] = Find(S, S[X]); 7 }
转自：http://blog.csdn.net/spch2008/article/details/9338943
数据结构与算法分析（四）——不相交集