大连理工大学算法分析与设计ch6-5动态等价关系-2s-[兼容模式]

6.6动态等价关系与并查集等价类的表示数组单链表树等价类的表示—数组数组记录每个数据元素所属等价类的编号Find(x)—O（1）Union（x,y）--O(n):修改其中一个等价类中所有数据元素的等价类编号n个顶点m条边kruscal算法构造最小生成树：O(2m)+O(mlogm)+O(n2)v0v1v2v3v4v56155536624v0v1v2v3v4v5datalabel001122334455(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)v0v1v2v3v4v56155536624v0v1v2v3v4v5datalabel001122334455(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)v0v1v2v3v4v56155536624v0v1v2v3v4v5datalabel001120334455(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)v0v1v2v3v4v56155536624v0v1v2v3v4v5datalabel001120334455(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)v0v1v2v3v4v56155536624v0v1v2v3v4v5datalabel001120334453(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)v0v1v2v3v4v56155536624v0v1v2v3v4v5datalabel001120334453(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)v0v1v2v3v4v56155536624v0v1v2v3v4v5datalabel001120334153(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)v0v1v2v3v4v56155536624v0v1v2v3v4v5datalabel001120334153(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)v0v1v2v3v4v56155536624v0v1v2v3v4v5datalabel001120304150(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)v0v1v2v3v4v56155536624v0v1v2v3v4v5datalabel001120304150(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)v0v1v2v3v4v56155536624v0v1v2v3v4v5datalabel001120304150(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)v0v1v2v3v4v56155536624v0v1v2v3v4v5datalabel001120304150(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)v0v1v2v3v4v56155536624v0v1v2v3v4v5datalabel011121314151(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)nn次次MAKEMAKE操作操作----------O(O(nn22))等价类的表示—链表单链表中每个结点:data,head,next,last数组实现“静态”链表Find(x)—O（1）Union(x,y)—将x和y所在的等价类对应的2个单链表合并成一个点链表，并修改其中一个单链表中所有数据元素的head值----小表合并到大表n个顶点m条边kruscal算法构造最小生成树：O(2m)+O(mlogm)+O(mlogn)v0v1v2v3v4v56155536624v0v1v2v3v4v5等价类的表示—链表(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)dataheadlastnext000-1111-1222-1333-1444-1555-1v0v1v2v3v4v56155536624v0v1v2v3v4v5等价类的表示—链表(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)dataheadlastnext000-1111-1222-1333-1444-1555-1v0v1v2v3v4v56155536624v0v1v2v3v4v5等价类的表示—链表(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)dataheadlastnext0022111-1202-1333-1444-1555-1v0v1v2v3v4v56155536624v0v1v2v3v4v5等价类的表示—链表(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)dataheadlastnext0022111-1202-1333-1444-1555-1v0v1v2v3v4v56155536624v0v1v2v3v4v5等价类的表示—链表dataheadlastnext0022111-1202-13355444-1535-1(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)v0v1v2v3v4v56155536624v0v1v2v3v4v5等价类的表示—链表dataheadlastnext0022111-1202-13355444-1535-1(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)v0v1v2v3v4v56155536624v0v1v2v3v4v5等价类的表示—链表(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)dataheadlastnext00221144202-13355414-1535-1v0v1v2v3v4v56155536624v0v1v2v3v4v5等价类的表示—链表(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)dataheadlastnext00221144202-13355414-1535-1v0v1v2v3v4v56155536624v0v1v2v3v4v5等价类的表示—链表(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)dataheadlastnext0052114420233055414-1505-1v0v1v2v3v4v56155536624v0v1v2v3v4v5等价类的表示—链表(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)dataheadlastnext0052114420233055414-1505-1v0v1v2v3v4v56155536624v0v1v2v3v4v5等价类的表示—链表(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)dataheadlastnext0052114420233055414-1505-1v0v1v2v3v4v56155536624v0v1v2v3v4v5等价类的表示—链表(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)dataheadlastnext0052114420233055414-1505-1v0v1v2v3v4v56155536624v0v1v2v3v4v5等价类的表示—链表(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)dataheadlastnext0042104420233055404-15051改进为改进为O(O(nlognnlogn))最小生成树最小生成树----------O(O(mmlogmlogm)+O(2)+O(2mm)+O()+O(mmlognlogn))等价类的表示—树••一个等价类以一棵树一个等价类以一棵树((inin--TreeTree))的形式表示，的形式表示，树的根树的根结点标记等价类结点标记等价类。。••树采用树采用双亲双亲表示法存放，表示法存放，A[A[ii]]存放数据元素存放数据元素xxii在树在树中的双亲结点。中的双亲结点。SS划分为划分为22个等价类：个等价类：SS11={0,2,3,5}={0,2,3,5}，，SS22={4,1,6}={4,1,6}dataParent0-11420304-15064023541641602354160235{0,2,3,5}{0,2,3,5}与与{4,1,6}{4,1,6}合并合并union----O(1)dataParent0-1142030405064find----d+1次parentlookupv0v1v2v3v4v56155536624v0v1v2v3v4v5dataparent0-11-12-13-14-15-1(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)v0v1v2v3v4v56155536624v0v1v2v3v4v5(v0,v2),(v3,v5),(v1,v4),(v2,v5),(v2,v3),(v0,v3),(v1,v2),(v0,v1),(v2,v4),(v4,v5)dataparent0-11-12-13-14-15-1v