4

到目前为止，我所拥有的主要基于 Cormen 等人的“算法简介”的第 571 页。

我在 python 中有一个 Node 类，它代表一个集合：

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

这个实现将使用一个List节点作为森林（我愿意接受更好的方法来存储集合）。

Initialize()返回一个节点列表，我将其存储在变量中set并传递给其他函数。

Find在森林中搜索值并返回它出现的集合。我选择使用for s in range(len(set)):，以便在递归中我可以缩小传递的集合列表set[s:]。 

def Find(set, value):
    for s in range(len(set)):
        if value != set[s].parent:
            set[s].parent = Find(set[s:], set[s].parent)
        return set[s]

Merge通过找到它们并提升排名较高的集合来合并森林中的集合。 

def Merge(set, value1, value2):
    set_val_1 = Find(set, value1)
    set_val_2 = Find(set, value2)
    if set_val_1.rank > set_val_2.rank:
        set_val_2.parent = set_val_1
    else:
        set_val_1.parent = set_val_2
        if set_val_1.rank == set_val_2.rank:
            set_val_2.rank += 1

我在执行Finds 和Merges 时遇到了一些错误，即Find没有返回正确的集合，所以我不确定是否Merge也能正常工作。我会很感激一些帮助，以确保正确实施这些功能。

4

5 回答 5

3

您是否查看过任何其他现有的 实现？

于 2011-02-23T20:19:55.147 回答
2

我没有这本书的最新版本，但这看起来不太像一个不相交的森林。

我认为您的错误是认为森林必须存储在一个集合中，并且您必须遍历该集合才能对节点进行操作。移除并实施为set_Merge()Find()Find()

def Find(n):
    if n != n.parent:
        n.parent = Find(n.parent)
    return n.parent

就像书中一样。然后添加一个MakeSet()返回一个正确初始化的节点，也可能是一个SameSet()函数：

def SameSet(n1, n2):
    return Find(n1) == Find(n2)

您现在有一个工作的不相交集实现。

于 2011-02-23T20:40:54.240 回答
1

假设每个节点都被初始化为它自己的父节点：

def Find(node):
    while node is not node.parent:
        node = node.parent
    return node
于 2011-02-23T21:33:56.460 回答
0

使用这个实现作为起点，我创建了一个新的 python 类来处理不相交的集合，它还支持使用 MongoDb 的持久性。

例如，通过我的课程，您应该能够：

  • 创建一个 的实例UnionFind()，默认情况下使用 python 内置字典，然后consolidate()在 MongoDb 集合中决定你的结果
  • 从 MongoDb 集合创建 UnionFind 的实例并直接使用它。

您可能想检查github 上的代码。

干杯，西蒙娜

于 2014-03-10T13:40:08.670 回答
0

维基百科页面为不相交集数据结构的基本操作提供了伪代码。这是 Python 的直接端口（使用路径压缩和按等级联合）：

class Node:
    """Represents an element of a set."""
    def __init__(self, id):
        self.id = id
        self.parent = self
        self.rank = 0
        self.size = 1

    def __repr__(self):
        return 'Node({!r})'.format(self.id)


def Find(x):
    """Returns the representative object of the set containing x."""
    if x.parent is not x:
        x.parent = Find(x.parent)
    return x.parent


def Union(x, y):
    """Combines the sets x and y belong to."""
    xroot = Find(x)
    yroot = Find(y)

    # x and y are already in the same set
    if xroot is yroot:
        return

    # x and y are not in same set, so we merge them
    if xroot.rank < yroot.rank:
        xroot, yroot = yroot, xroot  # swap xroot and yroot

    # merge yroot into xroot
    yroot.parent = xroot
    xroot.size += yroot.size
    if xroot.rank == yroot.rank:
        xroot.rank = xroot.rank + 1

演示：

>>> a, b, c = map(Node, 'abc')
>>> Find(a), Find(b), Find(c)
(Node('a'), Node('b'), Node('c'))
>>> Find(a).size
1
>>> Union(a, b)
>>> Union(b, c)
>>> Find(a), Find(b), Find(c)
(Node('a'), Node('a'), Node('a'))
>>> Find(a).size
3
于 2018-08-26T18:19:47.840 回答