算法導(dǎo)論學(xué)習(xí)筆記－第二十一章－用于不相交集合的數(shù)據(jù)結(jié)構(gòu)

不相交集合數(shù)據(jù)結(jié)構(gòu)保持一組不相交的動態(tài)集合，每個集合通過一個代表來標(biāo)識，代表即集合中的某個成員。

一些操作：

MAKE-SET(x): 建立一個新的集合，其唯一成員為x。

UNION(x,y): 將包含x和y的動態(tài)集合合并為一個新的集合。

FIND-SET(x): 返回一個指針，指向包含x的集合的代表。

應(yīng)用：例如，確定一個無向圖中連通子圖的個數(shù)。

每一個集合用一個鏈表表示。每個鏈表中的第一個對象作為它所在集合的代表。

每一個對象的結(jié)構(gòu)：

1）集合成員

2）指向包含下一個集合成員的對象的指針

3）指向代表的指針

每個鏈表都包含head指針和tail指針，head指向鏈表的代表，tail指向鏈表中最后的對象。

MAKE-SET(x): O(1)，創(chuàng)建新鏈表，其僅有對象為x

FIND-SET(x): O(1)，返回x指向代表的指針

UNION(x,y): 將x所在的鏈表拼接到y(tǒng)所在鏈表的表尾。注意，對于原先x所在鏈表中的每一個對象，都需要更新其指向代表的指針。

加權(quán)合并啟發(fā)式策略：設(shè)每個表還包括了表的長度，合并時，總是把較短的表拼到較長的表上。

使用加權(quán)合并策略，對m個MAKE-SET, UNION和FIND-SET操作所構(gòu)成的序列（其中n個MAKE-SET操作，因此UNION操作的次數(shù)至多為n-1），花費(fèi)的總時間為O(m+nlgn)。

p[x] <- x

rank[x] <- 0

LINK(FIND-SET(x),FIND-SET(y))

if rank[x] > rank[y]

      then p[y] <- x

      else p[x] <- y

            if rank[x]=rank[y]

                 then rank[y] <- rank[y]+1

if x!=p[x]

      then p[x] <- FIND-SET(p[x])

return p[x]

FIND-SET采用了兩趟方法：一趟沿查找路徑上升，直至找到根；第二趟沿查找路徑下降，以便更新每個結(jié)點(diǎn)，使之直接指向根。

分析：當(dāng)同時采用按秩合并和路徑壓縮時，對m個MAKE-SET, UNION, FIND-SET的操作序列，總的運(yùn)行時間可看作與m成線性關(guān)系。

附錄：