联合查找算法不返回预期结果

Question

我使用此示例实现了以下联合查找算法：

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

也就是说，我希望最小的标签是父标签

有没有人可以指出为什么会这样，我能做些什么来获得预期的结果？

Answer 1

你想要 Union Find by Rank

法典

源

class UF:
"""An implementation of union find data structure.
It uses weighted quick union by rank with path compression.
"""
def __init__(self, N):
"""Initialize an empty union find object with N items.
Args:
N: Number of items in the union find object.
"""
self._id = list(range(N))
self._count = N
self._rank = [0] * N
def find(self, p):
"""Find the set identifier for the item p."""
id = self._id
while p != id[p]:
p = id[p] = id[id[p]]   # Path compression using halving.
return p
def count(self):
"""Return the number of items."""
return self._count
def connected(self, p, q):
"""Check if the items p and q are on the same set or not."""
return self.find(p) == self.find(q)
def union(self, p, q):
"""Combine sets containing p and q into a single set."""
id = self._id
rank = self._rank
i = self.find(p)
j = self.find(q)
if i == j:
return
self._count -= 1
if rank[i] < rank[j]:
id[i] = j
elif rank[i] > rank[j]:
id[j] = i
else:
id[j] = i
rank[i] += 1
def __str__(self):
"""String representation of the union find object."""
return " ".join([str(x) for x in self._id])
def __repr__(self):
"""Representation of the union find object."""
return "UF(" + str(self) + ")"

例

使用示例边。

N = 5
edges = [(1, 1), (2, 2), (2, 3), (3, 3), (4, 2), (4, 4)] 
uf = UF(N)
for p, q in edges:
uf.union(p, q)
uf.show()

输出

0 0
1 1
2 2
2 2
2 2

评论

在无向图中将自边显示为边并不常见。

因此，而不是

edges = [(1, 1), (2, 2), (2, 3), (3, 3), (4, 2), (4, 4)]

它更常见(即只是非自边缘(：

edges = [(2, 3), (4, 2)]

在这两种情况下，上述代码都会生成相同的输出。

由于未显示自边，因此无法从

self.n_edges = np.max(edges) + 1  # not normally correct 

通常指定顶点数。