python - 在 Python 中实现不相交集数据结构

Question

我正在做一个涉及集群的小项目，我认为这里给出的代码https://www.ics.uci.edu/~eppstein/PADS/UnionFind.py可能是我工作的一个很好的起点。但是，在我的工作中实施它时遇到了一些困难：

如果我制作一个包含所有集群 cluster=set([0,1,2,3,4,...,99]) 的集合（有 100 个点，数字标记它们），那么我想分组将数字放入簇中，我是否只需编写 cluster=UnionFind()？现在集群的数据类型是什么？
如何在集群上执行常规操作？例如，我想读取集群中的所有点（可能已组合在一起），但键入 print cluster 会导致 < main .UnionFind instance at 0x00000000082F6408>。我还想不断向集群添加新元素，我该怎么做？UnionFind()的具体方法需要写吗？
我如何知道一个组的所有成员及其成员之一被调用？比如 0,1,3,4 组合在一起，那么如果我调用 3，我希望它打印 0,1,3,4，我该怎么做呢？

谢谢

score 1 · Accepted Answer

这是一个关于如何使用提供的 UnionFind 类的小示例代码。

初始化

使用提供的类创建集合的唯一方法是使用FIND它，因为它仅在找不到某个点时为它创建一个集合。您可能想要创建一个初始化方法。

union_find = UnionFind()
clusters = set([0,1,2,3,4])
for i in clusters:
    union_find[i]

联盟

# Merge clusters 0 and 1
union_find.union(0, 1)
# Add point 2 to the same set
union_find.union(0, 2)

寻找

# Get the set for clusters 0 and 1
print union_find[0]
print union_find[1]

获取所有集群

# print all clusters and their sets
for cluster in union_find:
    print cluster, union_find[cluster]

笔记：

给定一个簇号，没有直接的方法可以让你得到所有的点。您可以遍历所有点并选择具有所需簇号的点。您可能希望修改给定的类以更有效地支持该操作。

1 回答 1