DSA第5章并查集和等价关系.ppt

《DSA第5章并查集和等价关系.ppt》由会员分享，可在线阅读，更多相关《DSA第5章并查集和等价关系.ppt（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、5.8 5.8 并查集与等价关系并查集与等价关系 利用集合可以求解等价关系利用集合可以求解等价关系问题。问题。 将给定的等价关系划分为等价将给定的等价关系划分为等价类的问题称为类的问题称为等价问题等价问题。 并查集并查集( (即即UFUF集合集合) )是求解这类问是求解这类问题的方法。题的方法。第五章第五章 树树5.8 5.8 并查集与等价关系并查集与等价关系第一页，编辑于星期六：五点 四十四分。5.8.1 5.8.1 并查集的定义并查集的定义 设集合设集合V=1,2,nV=1,2,n。 并查集并查集（ UFUF集合）是由一组互不相交的集合组成的一个集合结构集合）是由一组互不相交的集合组成的一

2、个集合结构 在在V V上的一个上的一个UFUF集合集合是这样的集合结构，它由若干子集合是这样的集合结构，它由若干子集合V V1 1,V,V2 2,V,Vm m组成组成，V V1 1 V V2 2 VVm m=V,=V,且且V Vi i V Vj j= = , ,当当i i j j和和i,j=1,mi,j=1,m。 可以看出，一个可以看出，一个UFUF集合是一个包含若干互不相交的子集合的集合结构。并查集合是一个包含若干互不相交的子集合的集合结构。并查集上有两个最基本运算：集上有两个最基本运算： Find(i)Find(i)和和Union(x,y)Union(x,y) 并查集的并查集的ADTADT

3、： ADT UFsetADT UFset Date:Date: 由若干互不相交的子集合组成的集合。由若干互不相交的子集合组成的集合。 Operations:Operations: Create(): Create(): 创建每个仅包含一个元素的子集合的创建每个仅包含一个元素的子集合的UFUF集合。集合。 Find(i): Find(i): 返回返回i i所在的子集合标识。所在的子集合标识。 Union(x,y): Union(x,y): 合并合并x x和和y y两个子集合。两个子集合。 第二页，编辑于星期六：五点 四十四分。5.8.2 5.8.2 并查集的存储表示并查集的存储表示一种简单的表示

4、集合的做法是：每个子集合用一个线性表表示一种简单的表示集合的做法是：每个子集合用一个线性表表示，同一个线性表中的元素属于同一个子集合。，同一个线性表中的元素属于同一个子集合。0 01 12 23 34 45 56 6-1-1 2 2 3 3-1-1 3 3 6 6-1-10 01 15 52 24 43 36 6UFUF集合的顺序存储表示集合的顺序存储表示parentparent第三页，编辑于星期六：五点 四十四分。并查集用并查集用树树和和森林森林表示。表示。树树表示子集合表示子集合森林森林表示并查集表示并查集UFUF集合集合树树/ /森林的存储用双亲表示法。森林的存储用双亲表示法。值表示该顶

5、点的双亲。值表示该顶点的双亲。值为值为-1-1的顶点是某个子集合的根。的顶点是某个子集合的根。第四页，编辑于星期六：五点 四十四分。UFUF集合的集合的C+C+类：类：Class UFsetClass UFset public: public: UFset(int mSIZE); UFset(int mSIZE); UFset() delete parent; UFset() delete parent; int Find(int i) const; int Find(int i) const; void Union(int x, int y); void Union(int x, int y

6、); private: private: int int * *parent;parent; int size; int size;5.8.35.8.3并查集类并查集类第五页，编辑于星期六：五点 四十四分。构造函数：构造函数：UFset:UFset(int mSize)UFset:UFset(int mSize) size=mSize; size=mSize; parent=new int size; parent=new int size; for(int i=0; isize; i+) for(int i=0; i=0; i=parenti); for(; parenti=0; i=par

7、enti); return i; return i;合并集合合并集合x,y:x,y:void UFset:Union(int x; int y)void UFset:Union(int x; int y) parentx=y; parentx=y;0 1 2 3 4 5 60 1 2 3 4 5 6-1 1 -1 -1 -1 1 -1-1 1 -1 -1 -1 1 -10 01 12 23 34 45 56 60 01 12 23 34 45 56 6-1-1 2 2 3 3-1-1 3 3 6 6-1-10 01 15 52 24 43 36 60 1 2 3 4 5 60 1 2 3 4

8、5 6-1 2 3 -1 2 3 6 6 3 6 -1 3 6 -10 01 12 23 34 45 56 6第七页，编辑于星期六：五点 四十四分。UnionUnion算法的改进：算法的改进：void UFset:Union(int x; int y)void UFset:Union(int x; int y) parentx=y; parentx=y;0 01 15 52 24 43 36 60 1 2 3 4 5 60 1 2 3 4 5 6-1 2 3 -1 2 3 -1-1 3 6 3 6 -1-10 1 2 3 4 5 60 1 2 3 4 5 6-1 2 3 -1 2 3 6 6

9、3 6 -1 3 6 -10 01 12 23 34 45 56 60 01 15 52 24 43 36 60 1 2 3 4 5 60 1 2 3 4 5 6-1 2 3 -1 3 6 -1 2 3 -1 3 6 3 3 为避免产生退化树而影响为避免产生退化树而影响FindFind的搜索的搜索效率，将效率，将结点少结点少的树并入的树并入结点多结点多的树的树。每棵树的高度不超过每棵树的高度不超过 loglog2 2n n +1 +1。为表达一棵子树中结点为表达一棵子树中结点的个数，用根结点的的个数，用根结点的parentparent域存放该子树中域存放该子树中结点的个数。结点的个数。0 01

10、 15 52 24 43 36 60 1 2 3 4 5 60 1 2 3 4 5 6-1 2 3 -1 2 3 -4-4 3 6 3 6 -2-20 01 15 52 24 43 36 60 1 2 3 4 5 60 1 2 3 4 5 6-1 2 3 -1 2 3 -6-6 3 6 3 6 3 3第八页，编辑于星期六：五点 四十四分。UFset:Union2(int x; int y)UFset:Union2(int x; int y) int temp=parentx+parenty; int temp=parentx+parenty; if(parentxparenty) if(par

11、entxparenty) parentx=y; parenty=temp; parentx=y; parenty=temp; else else parenty=x; parentx=temp; parenty=x; parentx=temp; ;0 01 15 52 24 43 36 60 1 2 3 4 5 60 1 2 3 4 5 6-1 2 3 -1 2 3 -4-4 3 6 3 6 -2-20 01 15 52 24 43 36 60 1 2 3 4 5 60 1 2 3 4 5 6-1 2 3 -1 2 3 -6-6 3 6 3 6 3 3第九页，编辑于星期六：五点 四十四分。Fi

12、ndFind算法的改进：算法的改进：UFset:Find(int i) constUFset:Find(int i) const for(; parenti=0; i=parenti); for(; parenti=0; i=parenti); return i; return i;UFset:Find2(int i) constUFset:Find2(int i) const int r, t, l; int r, t, l; for(r=i; parentr=0; r=parentr); for(r=i; parentr=0; r=parentr); if(i!=r) if(i!=r) f

13、or(t=i; parentt!=r; t=l) for(t=i; parentt!=r; t=l) l=parentt; parentt=r; l=parentt; parentt=r; return r; return r;0 01 15 52 24 43 36 60 1 2 3 4 5 60 1 2 3 4 5 6-1-1 2 3 2 3 -4-4 3 6 3 6 -2-20 01 15 52 24 43 36 60 1 2 3 4 5 60 1 2 3 4 5 6-1-1 3 3 3 3 -4-4 3 6 3 6 -2-2i ir r第十页，编辑于星期六：五点 四十四分。5.8.6 5

14、.8.6 按等价关系分组按等价关系分组并查集的应用。并查集的应用。利用利用UFUF集合，将元素按等价关系分组。集合，将元素按等价关系分组。设设S=0,1,2,3,4,5,6S=0,1,2,3,4,5,6元素集合；元素集合； R=0R=0 1,21,2 3,33,3 0,40,4 5,65,6 5S5S上的等价对；上的等价对； 0,1,2,30,1,2,3和和4,5,6S4,5,6S按等价关系分成的两个等价类。按等价关系分成的两个等价类。分组算法：分组算法：(1)(1)每个元素单独一组；每个元素单独一组；(2)(2)输入一个等价对输入一个等价对i i j j；(3)(3)执行执行x=Find(i

15、); y=Find(j)x=Find(i); y=Find(j)；(4)(4)若若x x y,y,则执行则执行Union(x,y)Union(x,y)；(5)(5)重复重复(2)(2) (4)(4)，直到等价对输入完毕结束。，直到等价对输入完毕结束。第十一页，编辑于星期六：五点 四十四分。等价关系分组示例：等价关系分组示例：R=0R=0 1,21,2 3,33,3 0,40,4 5,65,6 550 01 12 23 34 45 56 6(a)(a)初始时初始时, ,输入输入0 0 1 10 01 12 23 34 45 56 6(b)(b)合并合并0 0和和1 1，输入输入2 2 3 30 01 12 23 34 45 56 6(c)(c)合并合并2 2和和3 3，输入输入3 3 0 0(d)(d)合并合并3 3和和1 1，输入输入4 4 5 50 01 12 23 34 45 56 60 01 12 23 34 45 56 6(e)(e)合并合并4 4和和5 5，输入输入6 6 5 50 01 12 23 34 45 56 6(f)(f)合并合并6 6和和5 5第十二页，编辑于星期六：五点 四十四分。第十三页，编辑于星期六：五点 四十四分。