之前，已經學會了Linked List, 並且知道如何用Linked List來實作Queue 和 Stack。
今天，我們將用Python list來實現Disjoint Set (併查集，另外也有人稱之為Union-Find)。
Disjoint Set適合用於處理一些子集合的合併和根節點的查找操作。
這種資料結構在圖論中非常有用，特別是在解決連通性相關問題的應用。
定義
一個森林狀的資料結構。
一開始，每個ID對應到一顆樹，根節點都指向自己。
整體看，就是有n顆樹(Tree)構成的森林(Forest)。
支援的操作與介面
DS.__init__(self, size)
初始化Disjoint Set，大小為參數size所指定
一開始，每個ID對應到一顆樹，根節點都指向自己。
整體看，就是有n顆樹(Tree)構成的森林(Forest)。
DS.find(x)
尋找ID x所在的根節點(代表屬於哪個集合)
DS.union(x, y)
合併ID x所在的集合 和 ID y所在的集合。
通常合併時，會以集合的size(也有課本稱之為rank)為依據。
size小的合併到size大的。
如果size相同，則合併到前者x所在的集合。
優點
1.使用path-compression之後，可以在 O (α(N)) ~ O(1) 常數時間內find()。
2.使用path-compression之後，可以在 O (α(N)) ~ O(1) 常數時間內union()。
缺點
1.相對不直覺，需要以陣列或字典去記錄每個ID的根結點。
Disjoint Set的class定義 與 建構子(初始化函式)
class DisjointSet:
def __init__(self, size):
self.parent = list(range(size))
self.rank = [1] * size
Disjoint Set常見的function實現
1.find(x)
尋找ID x所在的根節點(代表屬於哪個集合)。
並且沿路順便更新，把長輩節點的根結點都指向最上層的root。
這種技巧稱之為path compression。
時間複雜度: O (α(N)) ~ O(1) 常數時間
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # 路徑壓縮
return self.parent[x]
2.union(x, y)
合併ID x所在的集合 和 ID y所在的集合。
通常合併時，會以集合的size(也有課本稱之為rank)為依據。
size小的合併到size大的。
如果size相同，則合併到前者x所在的集合。
時間複雜度: O (α(N)) ~ O(1) 常數時間
def union(self, x, q):
rootX = self.find(x)
rootY = self.find(q)
if rootX != rootY:
# 按size (rank)合併
if self.rank[rootX] > self.rank[rootY]:
self.parent[rootY] = rootX
elif self.rank[rootX] < self.rank[rootY]:
self.parent[rootX] = rootY
else:
self.parent[rootY] = rootX
self.rank[rootX] += 1
完整的Disjoint Set實作和程式碼，
底層是Python dictionary。
class DisjointSet:
def __init__(self, size):
self.parent = list(range(size))
self.rank = [1] * size
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # 路徑壓縮
return self.parent[x]
def union(self, x, q):
rootX = self.find(x)
rootY = self.find(q)
if rootX != rootY:
# 按size (rank)合併
if self.rank[rootX] > self.rank[rootY]:
self.parent[rootY] = rootX
elif self.rank[rootX] < self.rank[rootY]:
self.parent[rootX] = rootY
else:
self.parent[rootY] = rootX
self.rank[rootX] += 1
def test():
# Example
# ID = 0, 1, 2, ..., 9
ds = DisjointSet(10)
print("After initialization")
for i in range(10):
print(f"root of {i} = {ds.find(i)}")
ds.union(1, 2)
print("\nAfter union(1, 2)")
for i in range(10):
print(f"root of {i} = {ds.find(i)}")
ds.union(3, 4)
print("\nAfter union(1, 2) and union(3, 4)")
for i in range(10):
print(f"root of {i} = {ds.find(i)}")
ds.union(1, 3)
print("\nAfter union(1, 2), union(3, 4), union(1, 3)")
for i in range(10):
print(f"root of {i} = {ds.find(i)}")
if __name__ == '__main__':
test()
測試輸出
After initialization
root of 0 = 0
root of 1 = 1
root of 2 = 2
root of 3 = 3
root of 4 = 4
root of 5 = 5
root of 6 = 6
root of 7 = 7
root of 8 = 8
root of 9 = 9
After union(1, 2)
root of 0 = 0
root of 1 = 1
root of 2 = 1
root of 3 = 3
root of 4 = 4
root of 5 = 5
root of 6 = 6
root of 7 = 7
root of 8 = 8
root of 9 = 9
After union(1, 2) and union(3, 4)
root of 0 = 0
root of 1 = 1
root of 2 = 1
root of 3 = 3
root of 4 = 3
root of 5 = 5
root of 6 = 6
root of 7 = 7
root of 8 = 8
root of 9 = 9
After union(1, 2), union(3, 4), union(1, 3)
root of 0 = 0
root of 1 = 1
root of 2 = 1
root of 3 = 1
root of 4 = 1
root of 5 = 5
root of 6 = 6
root of 7 = 7
root of 8 = 8
root of 9 = 9
結語
Disjoint Set其實就是對應到數學中的集合、集合合併的操作。
讀著可以試著舉幾個小範例，用紙筆追蹤驗算法來驗證輸出結果，是否和預期相符合。