Ch8.1-7 Equivalence Relation, Union Algorithm, Path Compression

《Ch8.1-7 Equivalence Relation, Union Algorithm, Path Compression 》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、CHAPTER8THEDISJOINTSETADT§1EquivalenceRelations【Definition】ArelationRisdefinedonasetSifforeverypairofelements(a,b),a,bS,aRbiseithertrueorfalse.IfaRbistrue,thenwesaythataisrelatedtob.【Definition】Arelation,~,overaset,S,issaidtobeanequivalencerelationoverSiffitissymmetric,reflex

2、ive,andtransitiveoverS.【Definition】TwomembersxandyofasetSaresaidtobeinthesameequivalenceclassiffx~y.1/12§2TheDynamicEquivalenceProblemGivenanequivalencerelation~,decideforanyaandbifa~b.〖Example〗GivenS={1,2,3,4,5,6,7,8,9,10,11,12}and9relations:124,31,610,89,74,68,35,211

3、,1112.Theequivalenceclassesare{2,4,7,11,12},{1,3,5},{6,8,9,10}Algorithm:(Union/Find){/*step1:readtherelationsin*/InitializeNdisjointsets;while(readina~b){if(!(Find(a)==Find(b)))Unionthetwosets;}/*end-while*/Dynamic(on-line)/*step2:decideifa~b*/while(readinaandb)if(Find(a)==Fi

4、nd(b))output(true);elseoutput(false);}2/12§2TheDynamicEquivalenceProblemElementsofthesets:1,2,3,...,NSets:S,S,......andSS=(ifij)——disjoint12ij〖Example〗S={6,7,8,10},S={1,4,9},S={2,3,5}123Note:1042Pointersarefromchildren6781935toparentsApossibleforestrepresentationofthesese

5、tsOperations:(1)Union(i,j)::=ReplaceSandSbyS=SSijij(2)Find(i)::=FindthesetSwhichcontainstheelementi.k3/12§3BasicDataStructureUnion(i,j)Idea:MakeSasubtreeofS,orviceversa.Thatis,wecanijsettheparentpointerofoneoftherootstotheotherroot.10467841019S1S219678S2S1Implementation1:

6、10678S1SS21name[]S24SS31922354/12§3BasicDataStructureImplementation2:S[element]=theelement’sparent.Note:S[root]=0andsetname=rootindex.〖Example〗Thearrayrepresentationofthethreesetsis104Hereweusethefactthat2S[1][2][3][4][5][6][7][8][9][10]678theelementsarenumberedfrom1to193

7、5402100N.210101040Hencetheycanbeusedasindicesofanarray.voidSetUnion(DisjSetS,(SSS)S[4]=10SetTypeRt1,121SetTypeRt2){S[Rt2]=Rt1;}Find(i)Implementation1:Implementation2:jSetTypeFind(ElementTypeX,name[k]SDisjSetS){for(;S[X]>0;X=S[X]);i...returnX;find(i)=‘S’}5/12§3BasicDataStr

8、uctureAnalysisPracticallyspeaking,unionandfindarealwayspaire