Python 中的不相交集实现

Question

我对 Python 比较陌生。我在研究Disjoint sets，实现如下：

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

现在在驱动代码中：

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):

这一行中设置了父项

self.parent[set1] = set2

我将 h 的父级设置为 i，从而将其从 bd 的集合中移除。如何实现一组 ihbd，其中 union() 中参数的顺序不会产生不同的结果？

Answer 1

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

这是一个正确的实现：

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

我还建议阅读 Disjoint-set data structure 以获取更多信息以及可能的优化。

Answer 2

为了加快实施速度，您可能希望在 find()

时更新父级

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

Python 中的不相交集实现

Disjoint set implementation in Python

algorithm

disjoint-sets

data-structures

python-3.x