資源描述:
《《并查集的定義》PPT課件.ppt》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、并查集并查集的定義在一些應(yīng)用問題中,我們需要?jiǎng)澐謓個(gè)不同的元素成若干組,每一組的元素構(gòu)成一個(gè)集合。這種問題的一個(gè)解決辦法是,在開始時(shí),讓每個(gè)元素自成一個(gè)單元素集合,然后按一定順序?qū)儆谕唤M的元素所在的集合合并。其間要反復(fù)用到查找一個(gè)元素在哪一個(gè)集合的運(yùn)算。適合于描述這類問題的抽象數(shù)據(jù)類型稱為并查集。(給出各個(gè)元素之間的聯(lián)系,要求將這些元素分成幾個(gè)集合,每個(gè)集合中的元素直接或間接有聯(lián)系。在這類問題中主要涉及的是對集合的合并和查找,因此將這種集合稱為并查集。)并查集的數(shù)學(xué)模型是若干不相交的動(dòng)態(tài)集合的集合S={A,B,C,.
2、..},它支持以下的運(yùn)算:(1)INITIAL(A,x):構(gòu)造一個(gè)取名為A的集合,它只包含一個(gè)元素x;(2)MERGE(A,B):將集合A和B合并,其結(jié)果取名為A或B;(3)FIND(x):找出元素x的所在集合,并返回該集合的名字。并查集的數(shù)學(xué)模型例如,對于S={1,2,...,7},要求作出S的等價(jià)類劃分滿足給定的等價(jià)性條件:1≡2,5≡6,3≡4,和1≡4。我們首先將S的每一個(gè)元素看成一個(gè)等價(jià)類,然后順序地處理所列的條件。每處理完一個(gè)條件,所得到的相應(yīng)等價(jià)類列表如下:1≡2{1,2}{3}{4}{5}{6}{7};5
3、≡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}。所得到的結(jié)果是{1,2,3,4}{5,6}{7}。用數(shù)組實(shí)現(xiàn)并查集Constmaxn=100;Vardata:array[1..maxn]ofinteger;在一般情況下,data應(yīng)定義為:array[元素的子界類型]of集合名的類型。合并:O(n)查找:O(1)將所有元素合并到一個(gè)集合:O(n2)建立一個(gè)集合O(1)procedureinitial(A,x:integer);begindat
4、a[x]:=A;end;構(gòu)造一個(gè)取名為A的集合,它只包含一個(gè)元素x;查找一個(gè)元素所屬集合O(1)functionfind(x:integer):integer;beginfind:=data[x];end;找出元素x的所在集合,并返回該集合的名字。合并兩個(gè)集合O(n)proceduremerge(A,B:integer);vari:integer;beginfori:=1tondoifdata[i]=Bthendata[i]:=A;end;將集合A和B合并,其結(jié)果取名為AConstmaxn=100;Vardata:arr
5、ay[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;用鏈表實(shí)現(xiàn)并查集合并:O(i)查找:O(1)將所有元素合并到一個(gè)集合:O(nlogn)從n個(gè)單元素
6、集開始,至多執(zhí)行n-1次的MERGE運(yùn)算就可以將所有元素合并到一個(gè)集合中。用前面算法,執(zhí)行n-1次MERGE運(yùn)算需要O(n2)時(shí)間,效率太低。加速M(fèi)ERGE運(yùn)算的一種方法是將各個(gè)集合中的元素鏈接成一個(gè)表,使得當(dāng)要把集合B合并到集合A上去的時(shí)候,只要遍歷B的各個(gè)元素而不必遍歷全部n個(gè)元素。但最壞情況下,合并所有元素的時(shí)間復(fù)雜度仍為O(n2)為了改善最壞情況下的復(fù)雜度,明顯的策略是:每次合并時(shí)總是將小的集合合并到大的集合上去。data=recordsetheaders:array[1..n]ofrecordcount:1..
7、n;{集合中元素的個(gè)數(shù)}firstelement:1..n;{第一個(gè)元素}end;names:array[1..n]ofrecordSetname:1..n;{該元素所屬集合}nextelement:1..n{該元素的下一個(gè)元素}endend;例:集合1為{1,3,4},集合2為{2},集合5為{5,6}。311200002500132014105650123456123456setheaders:names:procedureINITIAL(A:nametype;x:elementtype;varC:data);beg
8、inC.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;