用Python实现不相交集数据结构

Question

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

1. 如果我创建一个包含所有clusters cluster=set（[0,1,2,3,4，…，99]）的集合（有100个用数字标记的点），那么我想将这些数字分组到cluster中，我是否只需编写cluster=UnionFind（）？现在集群的数据类型是什么？

2. 如何对集群上的set执行常规操作？例如，我想读取cluster中的所有点（可能已经组合在一起），但是在<；main中键入print cluster results；。我还想继续向集群添加新元素，我该怎么做？我需要为UnionFind（）编写具体的方法吗？

3. 我怎么知道一个组的所有成员和其中一个成员被称为？例如，0,1,3,4被组合在一起，那么如果我调用3，我希望它打印0,1,3,4，我该怎么做？

谢谢

Answer 1

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

初始化

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

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

联合

^{pr2}$

查找

# 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]

注：

没有一种直接的方法可以让你在给定一个簇号的情况下得到所有的点。您可以在所有点上循环，并选择具有所需簇号的点。您可能需要修改给定的类以更有效地支持该操作。在