Python 替代实现中的不相交集森林 [英] Disjoint-Set forests in Python alternate implementation

问题描述

我正在用 Python 实现一个不相交的集合系统，但我遇到了障碍.我正在为系统使用树实现，并为系统实现 Find()、Merge() 和 Create() 函数.

I'm implementing a disjoint set system in Python, but I've hit a wall. I'm using a tree implementation for the system and am implementing Find(), Merge() and Create() functions for the system.

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

I am implementing a rank system and path compression for efficiency.

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

The catch is that these functions must take the set of disjoint sets as a parameter, making traversing hard.

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

The Create function takes in a list of values and returns a list of singular Nodes containing the appropriate data.

我认为 Merge 函数看起来与此类似，

I'm thinking the Merge function would look similar to this,

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) 将是原型.

but I'm not sure how to implement the Find() function since it is required to take the list of Nodes and a value (not just a node) as the parameters. Find(set, value) would be the prototype.

我知道当一个节点被当作 Find(x) 的参数时如何实现路径压缩，但这种方法让我失望.

I understand how to implement path compression when a Node is taken as a parameter for Find(x), but this method is throwing me off.

任何帮助将不胜感激.谢谢.

Any help would be greatly appreciated. Thank you.

为了澄清而进行编辑.

推荐答案

显然 merge 函数应该应用于节点对.

Clearly merge function should be applied to pair of nodes.

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

So find function should take single node parameter and look like this:

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

还有维基百科有伪代码，很容易翻译成python.

Also wikipedia has pseudocode that is easily translatable to python.

这篇关于Python 替代实现中的不相交集森林的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！