資訊專欄INFORMATION COLUMN
摘要：并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合的合并及查詢問題。在構(gòu)造函數(shù)中新建一個(gè)數(shù)組，表示節(jié)點(diǎn)所在的集合的樹的高度。以上是實(shí)現(xiàn)一個(gè)簡單的并查集的方式。
并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合的合并及查詢問題。常常在使用中以森林來表示。
并查集有三種基本操作，獲得根節(jié)點(diǎn)，判斷兩節(jié)點(diǎn)是否連通，以及將兩不連通的節(jié)點(diǎn)相連（相當(dāng)于將兩節(jié)點(diǎn)各自的集合合并）
用UnionFind類來表示一個(gè)并查集，在構(gòu)造函數(shù)中，初始化一個(gè)數(shù)組parent，parent[i]表示的含義為，索引為i的節(jié)點(diǎn)，它的直接父節(jié)點(diǎn)為parent[i]。初始化時(shí)各個(gè)節(jié)點(diǎn)都不相連，因此初始化parent[i]=i，讓自己成為自己的父節(jié)點(diǎn)，從而實(shí)現(xiàn)各節(jié)點(diǎn)不互連。
def __init__(self, n):
self.parent = list(range(n))
由于parent[i]僅表示自己的直接父節(jié)點(diǎn)，查詢兩個(gè)節(jié)點(diǎn)是否相交需要比較它們的根節(jié)點(diǎn)是否相同。因此要封裝一個(gè)查詢自己根節(jié)點(diǎn)的方法。
def get_root(self, i):
while i != self.parent[i]:
i = self.parent[i]
return i
接下來可以通過來比較根節(jié)點(diǎn)是否相同來判斷兩節(jié)點(diǎn)是否連通。
def is_connected(self, i, j):
return self.get_root(i) == self.get_root(j)
當(dāng)要連通兩個(gè)節(jié)點(diǎn)時(shí)，我們要將其中一個(gè)節(jié)點(diǎn)的根節(jié)點(diǎn)的parent，設(shè)置為另一個(gè)節(jié)點(diǎn)的根節(jié)點(diǎn)。注意，連通兩個(gè)節(jié)點(diǎn)并非僅僅讓兩節(jié)點(diǎn)自身相連，實(shí)際上是讓它們所屬的集合實(shí)現(xiàn)合并。
def union(self, i, j):
i_root = self.get_root(i)
j_root = self.get_root(j)
self.parent[i_root] = j_root
接下來我們做兩個(gè)小優(yōu)化。
由于調(diào)用get_root時(shí)需要通過不斷找自己的直接父節(jié)點(diǎn)，來尋找根節(jié)點(diǎn)，如果這棵樹的層級過深，會(huì)導(dǎo)致性能受到嚴(yán)重影響。因此我們需要在union時(shí)，盡可能的減小合并后的樹的高度。
在構(gòu)造函數(shù)中新建一個(gè)數(shù)組rank，rank[i]表示節(jié)點(diǎn)i所在的集合的樹的高度。
因此，當(dāng)合并樹時(shí)，分別獲得節(jié)點(diǎn)i和節(jié)點(diǎn)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操作本身進(jìn)行優(yōu)化。
當(dāng)前每次執(zhí)行g(shù)et_root時(shí)，需要一層一層的找到自己的父節(jié)點(diǎn)，很費(fèi)時(shí)。由于根節(jié)點(diǎn)沒有父節(jié)點(diǎn)，并且文章開始處提到過如果一個(gè)節(jié)點(diǎn)沒有父節(jié)點(diǎn)，那么它的父節(jié)點(diǎn)就是自己，因此可以說只有根節(jié)點(diǎn)的父節(jié)點(diǎn)是自己本身?，F(xiàn)在我們加上一個(gè)判斷，判斷當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是否為根節(jié)點(diǎn)，如果不為根節(jié)點(diǎn)，就遞歸地將自己的父節(jié)點(diǎn)設(shè)置為根節(jié)點(diǎn)，最后返回自己的父節(jié)點(diǎn)。
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實(shí)現(xiàn)一個(gè)簡單的并查集的方式。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/45553.html
摘要：很顯然，我們可以使用并查集來求解。并查集是用來將一系列的元素分組到不相交的集合中，并支持合并和查詢操作。理論總是過于抽象化，下面我們通過一個(gè)例子來說明并查集是如何運(yùn)作的。采用這個(gè)方法，我們就可以寫出最簡單版本的并查集代碼。朋友圈問題現(xiàn)在有 105個(gè)用戶，編號為 1- 105。已知有 m 對關(guān)系，每一對關(guān)系給你兩個(gè)數(shù) x 和 y ，代表編號為 x 的用戶和編號為 y 的用戶是在一個(gè)圈子中，例如...
摘要：這樣就將一個(gè)集合的節(jié)點(diǎn)歸屬到同一個(gè)集合號下了。最后如果并查集中只有一個(gè)集合，則說明可以構(gòu)建樹。 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...
摘要：題目要求提供一個(gè)二維數(shù)組表示一張地圖，其中代表陸地，代表海洋。這里使用一個(gè)新的二維數(shù)組來表示對應(yīng)地圖上的元素屬于哪個(gè)并查集。在合并的時(shí)候先進(jìn)行判斷，如果二者為已經(jīng)相連的陸地，則無需合并，否則將新的二維數(shù)組上的元素指向所在的并查集。 題目要求 Given a 2d grid map of 1s (land) and 0s (water), count the number of isla...
閱讀 525·2023-04-26 00:33
閱讀 3549·2021-11-24 09:39
閱讀 2953·2021-09-22 15:34
閱讀 2325·2019-08-23 18:07
閱讀 2921·2019-08-23 18:04
閱讀 3710·2019-08-23 16:06
閱讀 2902·2019-08-23 15:27
閱讀 1620·2019-08-23 14:32
