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

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

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

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

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

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

    return i

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

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

當要連通兩個節(jié)點時，我們要將其中一個節(jié)點的根節(jié)點的parent，設置為另一個節(jié)點的根節(jié)點。注意，連通兩個節(jié)點并非僅僅讓兩節(jié)點自身相連，實際上是讓它們所屬的集合實現(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

接下來我們做兩個小優(yōu)化。

由于調用get_root時需要通過不斷找自己的直接父節(jié)點，來尋找根節(jié)點，如果這棵樹的層級過深，會導致性能受到嚴重影響。因此我們需要在union時，盡可能的減小合并后的樹的高度。

在構造函數(shù)中新建一個數(shù)組rank，rank[i]表示節(jié)點i所在的集合的樹的高度。

因此，當合并樹時，分別獲得節(jié)點i和節(jié)點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操作本身進行優(yōu)化。

當前每次執(zhí)行get_root時，需要一層一層的找到自己的父節(jié)點，很費時。由于根節(jié)點沒有父節(jié)點，并且文章開始處提到過如果一個節(jié)點沒有父節(jié)點，那么它的父節(jié)點就是自己，因此可以說只有根節(jié)點的父節(jié)點是自己本身?，F(xiàn)在我們加上一個判斷，判斷當前節(jié)點的父節(jié)點是否為根節(jié)點，如果不為根節(jié)點，就遞歸地將自己的父節(jié)點設置為根節(jié)點，最后返回自己的父節(jié)點。

  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實現(xiàn)一個簡單的并查集的方式。希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

最新評論