我对 Python 比较陌生。我正在研究不相交集,并按如下方式实现:
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()
中参数的顺序不会产生不同的结果?
最佳答案
您的程序无法正常工作,因为您误解了不相交集实现的算法。 Union 是通过修改 root 节点的父节点而不是作为输入提供的节点来实现的。正如您已经注意到的,盲目修改您在输入中收到的任何节点的父节点只会破坏之前的并集。
这是一个正确的实现:
def union(self, set1, set2):
root1 = self.find(set1)
root2 = self.find(set2)
self.parent[root1] = root2
我还建议阅读 Disjoint-set data structure了解更多信息以及可能的优化。
关于python-3.x - Python 中的不相交集实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54039935/