我使用this示例实现了以下联合查找算法:
import numpy as np
class UnionFind(object):
def __init__(self, edges):
self.edges = edges
self.n_edges = np.max(edges) + 1
self.data = list(range(self.n_edges))
def find(self, i):
if i != self.data[i]:
self.data[i] = self.find(self.data[i])
return self.data[i]
def union(self, i, j):
pi, pj = self.find(i), self.find(j)
if pi != pj:
self.data[pi] = pj
def run(self):
for i, j in self.edges:
self.union(i, j)
labels = dict()
for i in range(self.n_edges):
labels[i] = self.find(i)
for k, v in labels.items():
print(k, v)
if __name__ == '__main__':
edges = [(1, 1), (2, 2), (2, 3), (3, 3), (4, 2), (4, 4)] // pairs of equivalent labels
uf = UnionFind(edges)
uf.run()
我希望结果是
0 0
1 1
2 2
3 2
4 2
但是上面的算法返回
0 0
1 1
2 3
3 3
4 3
也就是说,我希望最小的标签是父标签
有没有人能指出为什么会出现这种情况,以及我能做些什么来获得预期的结果
你想要Union-Find by Rank
代码
Source
示例
使用示例边
输出
评论
在无向图中,将自边显示为边并不常见
因此,而不是
更常见的情况是(即,只有非自边):
在任何一种情况下,上述代码都会产生相同的输出
由于未显示自边,因此无法从中获取顶点数
通常指定顶点数
相关问题 更多 >
编程相关推荐