0

我正在用 Python 实现一个不相交的集合系统，但我碰壁了。我正在为系统使用树实现，并且正在为系统实现 Find()、Merge() 和 Create() 函数。

我正在实施等级系统和路径压缩以提高效率。

问题是这些函数必须将不相交的集合作为参数，使得遍历变得困难。

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 函数接受一个值列表并返回一个包含适当数据的奇异节点列表。

我在想 Merge 函数看起来与此类似，

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

但我不确定如何实现 Find() 函数，因为它需要将节点列表和一个值（不仅仅是一个节点）作为参数。Find(set, value) 将是原型。

我了解当将节点作为 Find(x) 的参数时如何实现路径压缩，但是这种方法让我失望。

任何帮助将不胜感激。谢谢你。

为澄清而编辑。

4

3 回答 3

2

The implementation of this data structure becomes simpler when you realize that the operations union and find can also be implemented as methods of a disjoint set forest class, rather than on the individual disjoint sets.

If you can read C++, then have a look at my take on the data structure; it hides the actual sets from the outside world, representing them only as numeric indices in the API. In Python, it would be something like

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

(Not tested.)

If you choose not to follow this path, the client of your code will indeed have to have knowledge of Nodes and Find must take a Node argument.

于 2012-02-28T20:06:51.357 回答
1

显然merge功能应该应用于节点对。

所以find函数应该采用单节点参数，如下所示：

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

维基百科也有很容易翻译成 python 的伪代码。

于 2012-02-28T19:46:11.310 回答
0

查找总是在一个项目上完成。Find(item) 被定义为返回该项目所属的集合。这样的合并不能使用节点，合并总是需要两个项目/集。合并或联合（item1，item2）必须首先找到（item1）和find（item2），这将返回它们各自所属的集合。之后，由向上树表示的较小的集合必须添加到较高的集合中。发出 find 时，始终回溯路径并压缩它。

一个经过测试的路径压缩实现在这里。

于 2015-11-10T15:31:26.163 回答