算法導論學習筆記－第二十一章－用于不相交集合的數據結構

ID:107189 · 發表于 2016-3-5 18:14

總結：這一章講了并查集的相關概念，以及主要的MAKE-SET, UNION, FIND-SET操作，并給出了并查集的鏈表表示和森林表示方式。

1. 不相交集合上的操作

不相交集合數據結構保持一組不相交的動態集合，每個集合通過一個代表來標識，代表即集合中的某個成員。

一些操作：

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

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

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

應用：例如，確定一個無向圖中連通子圖的個數。

2. 不相交集合的鏈表表示

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

每一個對象的結構：

1）集合成員

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

3）指向代表的指針

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

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

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

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

加權合并啟發式策略：設每個表還包括了表的長度，合并時，總是把較短的表拼到較長的表上。

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

3. 不相交集合森林

利用有根樹來表示集合，每棵樹表示一個集合。樹中的每個成員僅指向其父節點，樹的根的父節點仍是自己，且樹的根即集合的代表。

啟發式策略：
1）按秩合并
合并時，使包含較少結點的樹的根指向包含較多結點的樹的根。秩，結點高度的上界。因此，即，具有較小秩的根在UNION操作中要指向具有較大秩的根。

2）路徑壓縮
在FIND-SET操作中，使查找路徑上的每個結點都直接指向根節點。

設rank[x]表示結點的秩，即x的高度的上界，p[x]表示x的父節點

偽代碼
MAKE-SET(x)

p[x] <- x

rank[x] <- 0

偽代碼
UNION(x,y)

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

偽代碼
LINK(x,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

偽代碼
FIND-SET(x)

if x!=p[x]