《并查集的定義》PPT課件.ppt

《并查集的定義》PPT課件.ppt

ID:52081682

大?。?86.84 KB

頁數(shù):45頁

時(shí)間:2020-03-31

《并查集的定義》PPT課件.ppt_第1頁
《并查集的定義》PPT課件.ppt_第2頁
《并查集的定義》PPT課件.ppt_第3頁
《并查集的定義》PPT課件.ppt_第4頁
《并查集的定義》PPT課件.ppt_第5頁
資源描述:

《《并查集的定義》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;

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動(dòng)畫的文件,查看預(yù)覽時(shí)可能會(huì)顯示錯(cuò)亂或異常,文件下載后無此問題,請放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負(fù)責(zé)整理代發(fā)布。如果您對本文檔版權(quán)有爭議請及時(shí)聯(lián)系客服。
3. 下載前請仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時(shí)可能由于網(wǎng)絡(luò)波動(dòng)等原因無法下載或下載錯(cuò)誤,付費(fèi)完成后未能成功下載的用戶請聯(lián)系客服處理。