Python中的不相交集森林替代實現

我在Python中實現了一個不相交集合系統，但是我碰到了一堵牆。我爲系統使用樹實現，併爲系統實現Find（），Merge（）和Create（）函數。Python中的不相交集森林替代實現

我正在實施排名系統和路徑壓縮以提高效率。

美中不足的是，這些功能必須採取一套獨立集合作爲參數，使得遍歷硬盤。

class Node(object): 
    def __init__(self, value): 
     self.parent = self 
     self.value = value 
     self.rank = 0 

def Create(values): 
    l = [Node(value) for value in values] 
    return l

Create函數接受值列表並返回包含適當數據的單數節點列表。

我想合併功能將類似於此，

def Merge(set, value1, value2): 
    value1Root = Find(set, value1) 
    value2Root = Find(set, value2) 
    if value1Root == value2Root: 
     return 
    if value1Root.rank < value2Root.rank: 
     value1Root.parent = value2Root 
    elif value1Root.rank > value2Root.rank: 
     value2Root.parent = value1Root 
    else: 
     value2Root.parent = value1Root 
     value1Root.rank += 1

，但我不知道如何，因爲它需要採取節點和一個列表執行查找（）函數值（不只是一個節點）作爲參數。查找（集合，值）將是原型。

我明白如何實現路徑壓縮當一個節點爲例進行查找（x）的參數，但這種方法是扔我。

任何幫助將不勝感激。謝謝。

編輯澄清。

來源

2012-02-28 Christian Benincasa

顯然merge功能應適用於配對節點。

所以find功能應該採取單個節點參數是這樣的：

def find(node): 
    if node.parent != node: 
     node.parent = find(node.parent) 
    return node.parent

而且wikipedia has pseudocode，很容易翻譯到Python。

來源

2012-02-28 19:46:11 Odomontois

謝謝。我知道這個實現應該如何處理作爲參數傳遞的節點，然而，這個實現需要這些參數是被搜索和合並的值。 – 2012-02-28 19:59:19

這種數據結構的實現，當你意識到，工會運作，發現也可以實現爲分離集森林類的方法，而不是對個人獨立集合變得更簡單。

如果你可以看到C++，然後看看my take on the data structure;它隱藏了來自外部世界的實際集合，僅將它們表示爲API中的數字索引。在Python中，它會像

class DisjSets(object): 
    def __init__(self, n): 
     self._parent = range(n) 
     self._rank = [0] * n 

    def find(self, i): 
     if self._parent[i] == i: 
      return i 
     else: 
      self._parent[i] = self.find(self._parent[i]) 
      return self._parent[i] 

    def union(self, i, j): 
     root_i = self.find(i) 
     root_j = self.find(j) 
     if root_i != root_j: 
      if self._rank[root_i] < self._rank[root_j]: 
       self._parent[root_i] = root_j 
      elif self._rank[root_i] > self._rank[root_j]: 
       self._parent[root_j] = root_i 
      else: 
       self._parent[root_i] = root_j 
       self._rank[root_j] += 1

（未測試）。

如果您選擇不走這條路，你的代碼的客戶端確實需要有Node S和Find必備知識採取Node的說法。

來源

2012-02-28 20:06:51

查找總是在一個項目上完成。查找（項目）被定義爲返回項目所屬的集合。合併本身不能佔用節點，合併總是需要兩個項目/集合。合併或聯合（item1，item2）必須先找到（item1）並找到（item2），它將返回其中每個屬於的集合。之後，由上樹代表的較小集合必須被添加到較高。發現查找時，始終回溯路徑並壓縮它。

甲測試執行與路徑壓縮是here。

來源

2015-11-10 15:31:26

Python中的不相交集森林替代實現

回答

相關問題