Python 中的並集查詢演算法

Manav Narula 2023年1月30日 2022年5月18日
  1. 並集演算法
  2. 在 Python 中實現 Union-Find 演算法
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() 函式的變化,分別用於實現聯合排序和路徑壓縮技術。

Author: Manav Narula
Manav Narula avatar Manav Narula avatar

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

相關文章 - Python Algorithm