《并查集的定義》ppt課件-全文預覽
【正文】 nctionbegin請寫一個程序，對于我們的關于親戚關系的提問，以最快的速度給出答案?；蛟S你并不知道，你的某個朋友是你的親戚。親戚 beginC[y].parent0whiley:=x。y,tmp:nametype。FIND(x:elementtype。它的想法很簡單：在集合的查找過程中順便將樹的深度降低。C[A].parent:=B。thenBegin(A,B:nametype。find:=C[x].setname。x:=C[x].parent。varcount:=1。parent:=0。C[x].setname:=A。var用父親數(shù)組實現(xiàn)并查集procedure{以此節(jié)點為根的樹層數(shù) }record一個是集合中的元素到存放該元素的元素名的樹結點的映射；另一個是集合的名字到表示該集合的樹的樹根的映射。每個集合用一棵樹表示。end[i].setname:=A。[i].nextelement0i:=[B].firstelement。C:data)；VarprocedureFIND(x:elementtype。C.C.C.C.var3 11 20 00 02 50 01 32 01 415 65123456123456setheaders： names：procedureSetname： 1..n； {該元素所屬集合 }count： 1..n； {集合中元素的個數(shù) }為了改善最壞情況下的復雜度，明顯的策略是：每次合并時總是將小的集合合并到大的集合上去。thennmerge(A,B:integer)。end。initial(A,x:integer)。data:array[1..maxn]Vardata[i]:=A。doforvarend。find(x:integer):integer。集合名的類型。of所得到的結果是 {1,2,3,4}{5,6}{7}。(3)FIND(x)：找出元素 x的所在集合，并返回該集合的名字。(2)MERGE(A,B)：將集合 A和 B合并，其結果取名為 A或 B；(1)INITIAL(A,x)：構造一個取名為 A的集合，它只包含一個元素 x；并查集的數(shù)學模型是若干不相交的動態(tài)集合的集合 S＝ {A,B,C,...}，它支持以下的運算：適合于描述這類問題的抽象數(shù)據(jù)類型稱為并查集。查 其間要反復用到查找一個元素在哪一個集合的運算。 )例如，對于 S＝ {1,2,...,7}，要求作出 S的等價類劃分滿足給定的等價性條件 :1≡2， 5≡6， 3≡4，和 1≡4。每處理完一個條件，所得到的相應等價類列表如下 :1≡2{1,2}{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}。Vardata:array[1..maxn]ofbegin構造一個取名為 A的集合，它只包含一
教學課件相關推薦
鄂ICP備17016276號-1