Python 中的並集查詢演算法
本教程將討論如何在 Python 中實現 union-find 演算法。
並集演算法
在程式設計中，選擇最優的資料結構對於保證我們程式碼的高效效能非常重要。
union-find 資料結構用於記錄和跟蹤一組給定的值，這些值被劃分為許多不重疊的不相交子集。這種資料結構也稱為不相交子集。
它支援對子集的兩種操作，Find 和 Union。讓我們在下面討論它們。
Find 操作查詢給定元素的子集。它提供子集代表，通常是這個集合中的一個專案。
聯合操作合併兩個子集。只有當它們屬於同一集合時，它才會組合子集，然後兩個子集共享代表。
我們使用兩個 Find 操作來比較兩個元素並檢查它們是否屬於同一個子集。如果它們具有相同的代表，它們就有，然後我們執行 Union 操作以合併兩個元素所屬的兩個子集。
Union-Find 演算法具有不同的應用，例如查詢最小生成樹、檢測無向圖中的迴圈等。
在 Python 中實現 Union-Find 演算法
為了在 Python 中實現 Union-Find，我們使用樹的概念。樹的根可以作為代表，每個節點都會持有對其父節點的引用。
Union-Find 演算法將遍歷父節點到達根，並通過附加它們的根來組合兩棵樹。
例子：
class uf_ds:
parent_node = {}
def make_set(self, u):
for i in u:
self.parent_node[i] = i
def op_find(self, k):
if self.parent_node[k] == k:
return k
return self.op_find(self.parent_node[k])
def op_union(self, a, b):
x = self.op_find(a)
y = self.op_find(b)
self.parent_node[x] = y
def display(u, data):
print([data.op_find(i) for i in u])
u = [1, 3, 5, 7]
data = uf_ds()
data.make_set(u)
display(u, data)
data.op_union(1, 5)
display(u, data)
data.op_union(7, 1)
display(u, data)
輸出：
[1, 3, 5, 7]
[5, 3, 5, 7]
[5, 3, 5, 5]
在上面的示例中，我們在 Python 中實現了 Union-Find 演算法。我們建立一個類來表示一個不相交的集合。
此類定義聯合和查詢操作方法並顯示集合。在使用 Find 操作比較值之後，我們定義這個類的一個物件並使用 Union 操作組合樹。
注意每次操作後的結果。
然而，在上述實現的最壞情況下，時間複雜度變為線性。樹被串起來，並不比連結串列好。
因此，引入了兩種優化技術來改進 Union-Find 演算法。
第一個涉及樹的排序以改進 Union 操作。樹的深度會增加樸素方法的時間複雜度，因此這種技術確保我們將較小樹的根附加到較大的樹。
這將 Python 中 Union-Find 演算法的最壞情況時間複雜度提高到幾乎 O(Log(n))。
路徑壓縮是另一種用於提高 Python 中聯合查詢演算法效率的技術。這種方法旨在展平給定的樹並改進 Find 操作。
這旨在使發現的根節點成為節點 n 的父節點。這消除了遍歷直接節點的需要。
當節點 n 是給定子樹的根時，此壓縮下面的所有元素。
這兩種技術在提高聯合查詢演算法的時間複雜度方面是有效的，甚至低於 (OLog(n))。它們相互補充。
我們可以在我們的程式碼中實現它們，如下所示。
class ufds:
parent_node = {}
rank = {}
def make_set(self, u):
for i in u:
self.parent_node[i] = i
self.rank[i] = 0
def op_find(self, k):
if self.parent_node[k] != k:
self.parent_node[k] = self.op_find(self.parent_node[k])
return self.parent_node[k]
def op_union(self, a, b):
x = self.op_find(a)
y = self.op_find(b)
if x == y:
return
if self.rank[x] > self.rank[y]:
self.parent_node[y] = x
elif self.rank[x] < self.rank[y]:
self.parent_node[x] = y
else:
self.parent_node[x] = y
self.rank[y] = self.rank[y] + 1
def display(u, data):
print([data.op_find(i) for i in u])
u = [1, 3, 5, 7]
data = ufds()
data.make_set(u)
display(u, data)
data.op_union(1, 5)
display(u, data)
data.op_union(7, 1)
display(u, data)
輸出：
[1, 3, 5, 7]
[5, 3, 5, 7]
[5, 3, 5, 5]
注意 op_union() 和 op_find() 函式的變化，分別用於實現聯合排序和路徑壓縮技術。
Manav is a IT Professional who has a lot of experience as a core developer in many live projects. He is an avid learner who enjoys learning new things and sharing his findings whenever possible.
LinkedIn