python - 联合查找算法不返回预期结果
问题描述
我使用这个例子实现了以下联合查找算法:
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
也就是说,我希望最小的标签是父级
有没有人可以指出为什么会这样以及我可以做些什么来获得预期的结果?
解决方案
代码
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
通常指定顶点数。
推荐阅读
- python - UNIQUE 约束失败的 Django 模型
- sql-server - System.Data.SqlClient.SqlException - 无法通过 Management Studio 连接到 SQL Server
- android - 用于编辑大数据对象的不同视图类型的 RecyclerView
- ffmpeg - 优化 hevc_toolbox 编码,使其看起来像 ffmeg 中的 x265 编码
- c++ - 函数从指针 c++ 中获取错误的值并返回错误的答案
- javascript - 在 tumblr 问题中嵌入抽搐
- html - 顶部菜单 - 将一项向右对齐
- php - 从 Excel 中读取图像
- linux - 检查 aa 函数(bash)中的字符串是否只有数字、小写和“_”
- java - 如何访问 Firebase 数据库的这些部分?