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

一些操作：

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

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

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

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

每一個(gè)集合用一個(gè)鏈表表示。每個(gè)鏈表中的第一個(gè)對(duì)象作為它所在集合的代表。

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

1）集合成員

2）指向包含下一個(gè)集合成員的對(duì)象的指針

3）指向代表的指針

每個(gè)鏈表都包含head指針和tail指針，head指向鏈表的代表，tail指向鏈表中最后的對(duì)象。

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

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

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

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

使用加權(quán)合并策略，對(duì)m個(gè)MAKE-SET, UNION和FIND-SET操作所構(gòu)成的序列（其中n個(gè)MAKE-SET操作，因此UNION操作的次數(shù)至多為n-1），花費(fèi)的總時(shí)間為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采用了兩趟方法：一趟沿查找路徑上升，直至找到根；第二趟沿查找路徑下降，以便更新每個(gè)結(jié)點(diǎn)，使之直接指向根。

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

附錄：