在Python中實現不相交集數據結構

Question

我正在研究一個涉及集羣的小型項目，我認爲這裏給出的代碼https://www.ics.uci.edu/~eppstein/PADS/UnionFind.py可能是我工作的一個很好的起點。然而，我所遇到它實現我的作品一些困難：

1. 如果我讓我的包含所有簇集羣=集（[0,1,2,3,4一組，...， 99））（有100個數字標記它們的數字），那麼我想將這些數字分組爲簇，我只是寫了cluster = UnionFind（）？現在什麼是羣集的數據類型？

2. 如何執行羣集上的常規操作？例如，我想閱讀羣集中的所有點（可能已分組在一起），但輸入打印羣集結果爲< main .UnionFind instance at 0x00000000082F6408>。我還想不斷爲集羣添加新元素，我該怎麼做？我需要爲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] 

聯盟

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

注：

有，讓你給一個簇號的所有點沒有直接的方法。您可以遍歷所有點並挑選具有所需羣集編號的點。您可能需要修改給定的類以更有效地支持該操作。