python實現一個簡單的并查集

wawor4827 發布于2019-07-31 12:23 / 3247人閱讀

摘要：并查集是一種樹型的數據結構，用于處理一些不相交集合的合并及查詢問題。在構造函數中新建一個數組，表示節點所在的集合的樹的高度。以上是實現一個簡單的并查集的方式。

并查集是一種樹型的數據結構，用于處理一些不相交集合的合并及查詢問題。常常在使用中以森林來表示。

并查集有三種基本操作，獲得根節點，判斷兩節點是否連通，以及將兩不連通的節點相連（相當于將兩節點各自的集合合并）

用UnionFind類來表示一個并查集，在構造函數中，初始化一個數組parent，parent[i]表示的含義為，索引為i的節點，它的直接父節點為parent[i]。初始化時各個節點都不相連，因此初始化parent[i]=i，讓自己成為自己的父節點，從而實現各節點不互連。

    def __init__(self, n):
        self.parent = list(range(n))

由于parent[i]僅表示自己的直接父節點，查詢兩個節點是否相交需要比較它們的根節點是否相同。因此要封裝一個查詢自己根節點的方法。

    def get_root(self, i):
        while i != self.parent[i]:
            i = self.parent[i]

        return i

接下來可以通過來比較根節點是否相同來判斷兩節點是否連通。

    def is_connected(self, i, j):
        return self.get_root(i) == self.get_root(j)

當要連通兩個節點時，我們要將其中一個節點的根節點的parent，設置為另一個節點的根節點。注意，連通兩個節點并非僅僅讓兩節點自身相連，實際上是讓它們所屬的集合實現合并。

    def union(self, i, j):
        i_root = self.get_root(i)
        j_root = self.get_root(j)
        self.parent[i_root] = j_root

接下來我們做兩個小優化。
由于調用get_root時需要通過不斷找自己的直接父節點，來尋找根節點，如果這棵樹的層級過深，會導致性能受到嚴重影響。因此我們需要在union時，盡可能的減小合并后的樹的高度。
在構造函數中新建一個數組rank，rank[i]表示節點i所在的集合的樹的高度。

因此，當合并樹時，分別獲得節點i和節點j的root i_root和j_root之后，我們通過訪問rank[i_root]和rank[j_root]來比較兩棵樹的高度，將高度較小的那棵連到高度較高的那棵上。如果高度相等，則可以隨便，并將rank值加一。

    def union(self, i, j):
        i_root = self.get_root(i)
        j_root = self.get_root(j)

        if self.rank[i_root] == self.rank[j_root]:
            self.parent[i_root] = j_root
            self.rank[j_root] += 1
        elif self.rank[i_root] > self.rank[j_root]:
            self.parent[j_root] = i_root
        else:
            self.parent[i_root] = j_root

通過對union操作的改良可以防止樹的高度過高。我們還可以對get_root操作本身進行優化。
當前每次執行get_root時，需要一層一層的找到自己的父節點，很費時。由于根節點沒有父節點，并且文章開始處提到過如果一個節點沒有父節點，那么它的父節點就是自己，因此可以說只有根節點的父節點是自己本身。現在我們加上一個判斷，判斷當前節點的父節點是否為根節點，如果不為根節點，就遞歸地將自己的父節點設置為根節點，最后返回自己的父節點。

    def get_root(self, i):
        if self.parent[i] != self.parent[self.parent[i]]:
            self.parent[i] = self.get_root(self.parent[i])
        return self.parent[i]

以上是python實現一個簡單的并查集的方式。

GPU云服務器云服務器并查集 python實現簡單爬蟲功能簡單編寫一個html 您編一個簡單點的

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/45553.html

面試常考算法題之并查集問題

摘要：很顯然，我們可以使用并查集來求解。并查集是用來將一系列的元素分組到不相交的集合中，并支持合并和查詢操作。理論總是過于抽象化，下面我們通過一個例子來說明并查集是如何運作的。采用這個方法，我們就可以寫出最簡單版本的并查集代碼。朋友圈問題現在有 105個用戶，編號為 1- 105。已知有 m 對關系，每一對關系給你兩個數 x 和 y ，代表編號為 x 的用戶和編號為 y 的用戶是在一個圈子中，例如...

番茄西紅柿 2021-11-26 11:11 評論0 收藏2637
[Leetcode] Graph Valid Tree 圖與樹

摘要：這樣就將一個集合的節點歸屬到同一個集合號下了。最后如果并查集中只有一個集合，則說明可以構建樹。 Graph Valid Tree Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check w...

luqiuwen 2019-08-14 12:36 評論0 收藏0
leetcode200. Number of Islands

摘要：題目要求提供一個二維數組表示一張地圖，其中代表陸地，代表海洋。這里使用一個新的二維數組來表示對應地圖上的元素屬于哪個并查集。在合并的時候先進行判斷，如果二者為已經相連的陸地，則無需合并，否則將新的二維數組上的元素指向所在的并查集。題目要求 Given a 2d grid map of 1s (land) and 0s (water), count the number of isla...

Zoom 2019-08-16 10:45 評論0 收藏0