数据结构与算法分析课件chapter.pptxVIP

Chapter 8 The Disjoint Set ADT Equivalence 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 sets, x,y,z are elements in set ) :Reflexive x ?x.Symmetric x ?y,y ?xTransitive x ?y and y ?z,then x ?z Equivalence Class确定等价类的方法分两步走：读入并存储所有的等价对( i, j )；标记和输出所有的等价类。 void equivalence ( ) { 初始化; while ( 等价对未处理完 ) { 读入下一个等价对 ( i, j ); 存储这个等价对 ; } 输出初始化; for ( 尚未输出的每个对象 ) 输出包含这个对象的等价类 ;}Equivalence Class 2)Example: set s= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} pairs of equivalence: (0 4),(3 1),(6 10),(8 9),(7 4),(6 8),(3 5),(2 11)，(11 0) Initial:{0}，{1}，{2}，{3}，{4}，{5}，{6}，{7}，{8}， {9}, {10}，{11} 0?4 {0，4}，{1}，{2}，{3}，{4}，{5}，{6}，{7}，{8}， {9}, {10}， {11} 3 ?1 {0，4}，{1，3}，{2}，{4}，{5}，{6}，{7}，{8}，{9}， {10}， {11} Equivalence Class6 ?10 {0，4}，{1，3}，{2}，{4}，{5}，{6，10}，{7}， {8}，{9}， {11}8 ?9 {0，4}，{1，3}，{2}，{4}，{5}，{6，10}，{7}，{8， 9}， {11}7 ? 4 {0，4，7}，{1，3}，{2}，{5}，{6，10}，{8，9}， {11}6 ? 8 {0，4，7}，{1，3}，{2}，{5}，{6，8，9，10}， {11}3 ? 5 {0，4，7}，{1，3，5}，{2}，{6，8，9，10}，{11}2 ? 11 {0，4，7}，{1，3，5}，{2，11}，{6，8，9，10}11 ? 0 {0，4，7，2，11}，{1，3，5}，{6，8，9，10} Equivalence Class 3)并查集支持以下三种操作： Union (Root1, Root2) //合并操作 Find (x) //查找操作 UFSets (s) //构造函0 1 2 3 4 5 6 7 8 9 10 0 5 0 3 0 3 1 1 1 5parent Equivalence Class4) Tree Representation(Union-Find sets) Example: S1={1,7,8,9}, S2={5,2,10}, S3={3,4,6},they all belong to S={1,2,3,……,10}Equivalence Classsimple tree solution to union-find problem void Initialize(int n) { parent=new int[n+1]; for(int e=1;e=n;e++) parent[e]=0; } int Find(int e) { while(parent[e]) e=parent[e]; return e; } void Union(int i, int j) { parent[j]=i; } example:1531578921046789210 0 1 2 3 4 5 6 7 8 9 10 0 5 0 3 0 3 1 1 1 5parentEquivalen