并查集的定義ppt課件(編輯修改稿)
2025-06-08 08:20 本頁面
【文章內(nèi)容簡介】 60。begin{將 B合并到 A}i:=[B].firstelement。while[i].nextelement0dobegin[i].setname:=A。i:=[i].nextelement。end。[i].setname:=A。[i].nextelement:=[A].firstelement。[A].firstelement:=[B].firstelement。[A].count:=[A].count+[B].count。[B].count:=0。[B].firstelement:=0endelse{將 A合并到 B}End。用樹實現(xiàn)并查集每個集合用一棵樹表示。集合的元素名分別存放在樹的結(jié)點中。樹的每一個結(jié)點還存放著一個指向其父結(jié)點的指針。此外，還需要兩個映射。一個是集合中的元素到存放該元素的元素名的樹結(jié)點的映射；另一個是集合的名字到表示該集合的樹的樹根的映射。A＝ {1,2,3,4}， B＝ {5,6}和 C＝ {7}12 34567A＝ {1,2,3,4}， B＝ {5,6}和 C＝ {7}12 3456將 B合并到 A合并： O(1)查找： O(logn)將所有元素合并到一個集合 ： O(n)注：每次應(yīng)將小樹合并到大樹中，否則最壞情況下樹會退化成一條鏈，使查找的時間復(fù)雜度為O(n)。data=array[1..n]ofrecord{下標(biāo)為元素的子界類型 }setname:1..n。{集合名稱 }parent:1..n。count:1..n。{以此節(jié)點為根的樹層數(shù) }end。用父親數(shù)組實現(xiàn)并查集procedureINITIAL(A:nametype。x:elementtype。varC:data)。beginC[x].setname:=A。C[x].parent:=0。C[x].count:=1。end。functionFIND(x:elementtype。varC:data):nametype。BeginwhileC[x].parent0dox:=C[x].parent。find:=C[x].setname。end。procedureMERGE(A,B:nametype。varC:data)；Vari:elementtype。Begin查找 A的樹根元素 x,B的樹根元素 yifC[x].countC[y].countthenC[y].parent:=A{將 B合并到 A}elseC[A].parent:=B。1
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1