数据结构与算法分析b_课件chapter8

1、Chapter 8The Disjoint Set ADTEquivalence Class1)Definition of Equivalence Class:Suppose we have a set U=1,2,n of n elements and a set R=(i1,j1), (i2,j2) (ir,jr)of r relations. The relation R is an equivalence relation iff the following conditions are true(symbol represent the equivalence relation on

2、 sets, x,y,z are elements in set ) :Reflexive x x. Symmetric x y,y xTransitive x y and y z,then x zEquivalence Class确定等价类的方法分两步走：1. 读入并存储所有的等价对( i, j )；2. 标记和输出所有的等价类。void equivalence ( ) 初始化;while ( 等价对未处理完) 读入下一个等价对( i, j );存储这个等价对; 输出初始化;for ( 尚未输出的每个对象)输出包含这个对象的等价类;Equivalence Class2)Example:set

3、 s= 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11pairs of equivalence:(04),(31),(610),(89),(74),(68),(35),(211)，(110)Initial:0，1，2，3，4，5，6，7，8，9, 10，110，4，1，2，3，4，5，6，7，8， 9, 10，11043 1 0，4，1，3，2，4，5，6，7，8，9， 10，11Equivalence Class6 100，4，1，3，2，4，5，6，10，7，8，9，118 90，4，1，3，2，4，5，6，10，7，8，110，4，7，1，3，2，5，6，10，

4、8，9，110，4，7，1，3，2，5，6，8，9，10， 110，4，7，1，3，5，2，6，8，9，10，110，4，7，1，3，5，2，11，6，8，9，100，4，7，2，11，1，3，5，6，8，9，109，7 46 83 52 1111 0Equivalence Class3)并查集支持以下三种操作：u Union (Root1, Root2)/合并操作/查找操作/构造函数u Find (x)u UFSets (s)Equivalence Class4) Tree Representation(Union-Find sets) Example:S1=1,7,8,9, S2=5,2,

5、10, S3=3,4,6,they allbelong to S=1,2,3,10153789210461050102530435063718191parentEquivalence Classsimple tree solution to union-find problem void Initialize(int n) parent=new intn+1; for(int e=1;e=n;e+)parente=0;int Find(int e) while(parente)e=parente; return e;void Union(int i, int j) parentj=i;exam

6、ple:Equivalence Class153789210461050102530435063718191parent1Union ( 1,5 )5789210为简化讨论，忽略实际的集合名，仅用表示集合的树的根来标识集合。用构造函数UFSets(s) 构造一个森林, 每棵树只有一个结点, 表示集合中各元素自成一个子集合。下标parent0123456789-1-1-1-1-1-1-1-1-1-1下标parent0123456789集合 S1, S2 和 S3 的双亲表示-3 4-3 2-4 070S1618932520044S211S3-44-32-320004下标parent0123456

7、789集合 S1 S2 和 S3 的双亲表示0-78014-7 414806070404709049640S1 S2的可能的表示方法12-74-32020004Equivalence ClassJavapublic class DisjSetspublic DisjSets( int numElements ) public void union( int root1, int root2 ) public int find( int x )private int s;public DisjSets( int numElements )s = new int numElements ; for

8、( int i = 0; i s.length; i+ )s i = -1; /一个根结点Equivalence Classpublic void union( int root1, int root2 ) / 合并操作s root2 = root1;public int find( int x )/ 查找操作if( sx u,in the worst case a tree with m elements can have a height of m:Union(2,1),Union(3,2),Union(4,3),Union(5,4)54321Equivalence Class6)Perf

9、ormance Enhancementimprove Union in order to decrease the time each find take, so that the height of tree will not increase linearly .Equivalence Classtwo rules:Weight rule: if the number of nodes in tree i is less than the number in tree j, then make j the parent of i; otherwise,make i the parent o

10、f j.Height rule: if the height of tree i is less than that of tree j, then make j the parent of i; otherwise,make i the parent of j.Equivalence ClassLets discuss the weight rule(C+) :Parent1= -7115Union(1,5)Parent5=15789210789210Besides the parent field, each node has a boolean field root .The root

11、field is true iff the node is presently a root node.The parent field of each root node is used to keep a count of the total number of nodes in the tree.Equivalence ClassUnion with the weight rule void Initialize(int n) root=new booln+1; parent=new intn+1; for(int e=1;e=n;e+) parente=1; roote=true;in

12、t Find(int e) while(!roote)e=parente; return e;Equivalence Classvoid Union(int i, int j)if(parentiparentj)/i becomes subtree of j parentj=parentj+parenti; rooti=false;parenti=j;else parenti=parenti+parentj; rootj=false;parentj=i;Equivalence ClassJava(高度规则）用一个数组来实现，根结点中放负数，而且是代表高度。public void union(

13、int root1, int root2 )if(s root2 s root1 )s root1 = root2;else if( s root1 = = s root2 ) s root1 -;s roo2 = root1; 51378921046100123456789S:-25-23-231115Equivalence Class15789210union ( 1, 5 )sroot1- sroot2 = root115789210Equivalence Class.Improvement of Find path compression When processing a equivalence pair, we need tooperate Find twice, WeightUnion once.Example of improvement:11869797810Find(6)2102464Equivalenc