☘用Python來實現Disjoint Set (併查集/ Union-Find)

Joel & Jasmin Førestbird on Unsplash

之前，已經學會了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其實就是對應到數學中的集合、集合合併的操作。

讀著可以試著舉幾個小範例，用紙筆追蹤驗算法來驗證輸出結果，是否和預期相符合。

Disjoin Set相關的演算法練習題與詳解

🗿字典應用: Most Stones Removed with Same Row or Column_LC#947