Python中的不相交集实现 [英] Disjoint set implementation in Python

问题描述

我对Python比较陌生。我正在研究不连续集，并按如下方式实现它：

I am relatively new to Python. I am studying Disjoint sets, and implemented it as follows:

class DisjointSet:
    def __init__(self, vertices, parent):
        self.vertices = vertices
        self.parent = parent

    def find(self, item):
        if self.parent[item] == item:
            return item
        else:
            return self.find(self.parent[item])

    def union(self, set1, set2):
        self.parent[set1] = set2

现在在驱动程序代码中：

Now in the driver code:

def main():
    vertices = ['a', 'b', 'c', 'd', 'e', 'h', 'i']
    parent = {}

    for v in vertices:
        parent[v] = v

    ds = DisjointSet(vertices, parent)
    print("Print all vertices in genesis: ")
    ds.union('b', 'd')

    ds.union('h', 'b')
    print(ds.find('h')) # prints d (OK)
    ds.union('h', 'i')
    print(ds.find('i')) # prints i (expecting d)

main()

所以，首先我初始化了所有节点作为单独的不交集。然后将 bd 和 hb 结合在一起，形成集合： hbd 然后合并 hi ，这应该（按照我的假设）为我们提供集合： ihbd 。我了解由于将父级设置为 union（set1，set2）：

So, at first I initialized all nodes as individual disjoint sets. Then unioned bd and hb which makes the set: hbd then hi is unioned, which should (as I assumed) give us the set: ihbd. I understand that due to setting the parent in this line of union(set1, set2):

self.parent [set1] = set2

我正在设置 h 作为 i ，因此将其从 bd 的集合中删除。如何获得一组 ihbd ，其中 union（）中的参数顺序不会产生不同的结果？

I am setting the parent of h as i and thus removing it from the set of bd. How can I achieve a set of ihbd where the order of the params in union() won't yield different results?

推荐答案

您的程序无法正常运行，因为您误解了不连续集实现的算法。通过修改 root 节点的父节点而不是修改作为输入提供的节点来实现联合。正如您已经注意到的，盲目地修改输入中收到的任何节点的父节点只会破坏先前的并集。

Your program is not working correctly because you have misunderstood the algorithm for disjoint set implementation. Union is implemented by modifying the parent of the root node rather than the node provided as input. As you have already noticed, blindly modifying parents of any node you receive in input will just destroy previous unions.

这是一个正确的实现：

def union(self, set1, set2):
    root1 = self.find(set1)
    root2 = self.find(set2)
    self.parent[root1] = root2

我也建议阅读不相交集数据结构，以获取更多信息以及可能的优化。

I would also suggest reading Disjoint-set data structure for more info as well as possible optimizations.

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