《并查集的定义》PPT课件

《《并查集的定义》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、并查集并查集的定义在一些应用问题中，我们需要划分n个不同的元素成若干组，每一组的元素构成一个集合。这种问题的一个解决办法是，在开始时，让每个元素自成一个单元素集合，然后按一定顺序将属于同一组的元素所在的集合合并。其间要反复用到查找一个元素在哪一个集合的运算。适合于描述这类问题的抽象数据类型称为并查集。(给出各个元素之间的联系，要求将这些元素分成几个集合，每个集合中的元素直接或间接有联系。在这类问题中主要涉及的是对集合的合并和查找，因此将这种集合称为并查集。)并查集的数学模型是若干不相交的动态集合的集合S

2、＝{A,B,C,...}，它支持以下的运算：(1)INITIAL(A,x)：构造一个取名为A的集合，它只包含一个元素x；(2)MERGE(A,B)：将集合A和B合并，其结果取名为A或B；(3)FIND(x)：找出元素x的所在集合，并返回该集合的名字。并查集的数学模型例如，对于S＝{1,2,...,7}，要求作出S的等价类划分满足给定的等价性条件:1≡2，5≡6，3≡4，和1≡4。我们首先将S的每一个元素看成一个等价类，然后顺序地处理所列的条件。每处理完一个条件，所得到的相应等价类列表如下:1≡2{1,2

3、}{3}{4}{5}{6}{7}；5≡6{1,2}{3}{4}{5,6}{7}；3≡4{1,2}{3,4}{5,6}{7}；1≡4{1,2,3,4}{5,6}{7}。所得到的结果是{1,2,3,4}{5,6}{7}。用数组实现并查集Constmaxn=100;Vardata:array[1..maxn]ofinteger;在一般情况下，data应定义为：array[元素的子界类型]of集合名的类型。合并：O(n)查找：O(1)将所有元素合并到一个集合：O(n2)建立一个集合O(1)procedurein

4、itial(A,x:integer);begindata[x]:=A;end;构造一个取名为A的集合，它只包含一个元素x；查找一个元素所属集合O(1)functionfind(x:integer):integer;beginfind:=data[x];end;找出元素x的所在集合，并返回该集合的名字。合并两个集合O(n)proceduremerge(A,B:integer);vari:integer;beginfori:=1tondoifdata[i]=Bthendata[i]:=A;end;将集合A和

5、B合并，其结果取名为AConstmaxn=100;Vardata:array[1..maxn]ofinteger;procedureinitial(A,x:integer);begindata[x]:=A;end;functionfind(x:integer):integer;beginfind:=data[x];end;proceduremerge(A,B:integer);vari:integer;beginfori:=1tondoifdata[i]=Bthendata[i]:=A;end;用链表实

6、现并查集合并：O(i)查找：O(1)将所有元素合并到一个集合：O(nlogn)从n个单元素集开始，至多执行n-1次的MERGE运算就可以将所有元素合并到一个集合中。用前面算法，执行n-1次MERGE运算需要O(n2)时间，效率太低。加速MERGE运算的一种方法是将各个集合中的元素链接成一个表，使得当要把集合B合并到集合A上去的时候，只要遍历B的各个元素而不必遍历全部n个元素。但最坏情况下，合并所有元素的时间复杂度仍为O(n2)为了改善最坏情况下的复杂度，明显的策略是：每次合并时总是将小的集合合并到大的集

7、合上去。data＝recordsetheaders：array[1..n]ofrecordcount：1..n；{集合中元素的个数}firstelement：1..n;{第一个元素}end；names：array[1..n]ofrecordSetname：1..n；{该元素所属集合}nextelement：1..n{该元素的下一个元素}endend；例：集合1为{1,3,4}，集合2为{2}，集合5为{5,6}。311200002500132014105650123456123456setheaders

8、：names：procedureINITIAL(A:nametype;x:elementtype;varC:data);beginC.names[x].setname:=A;C.names[x].nextelement:=0;C.setheaders[A].count:=1;C.setheaders[A].firstelement.:=x;end;functionFIND(x:elementtype;varC:data):nametype;