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中的不相交集森林替代实现

回答

相关问题