作者:诚心诚意1997_514 | 来源:互联网 | 2023-02-01 08:03
目标:希望从大量集合中有效地查找所有断开连接的图形
例如,我有一个如下所示的数据文件:
A, B, C
C, D, E
A, F, Z
G, J
...
每个条目代表一组元素.第一个条目A,B,C = {A,B,C}这也表明A和B,A和C,B和C之间存在边缘.
我最初提出的算法如下
1.parse all the entries into a list:
[
{A,B,C}
{C,D,E}
...
]
2.start with the first element/set of the list can called start_entry, {A,B,C} in this case
3.traverse other element in the list and do the following:
if the intersection of the element and start_entry is not empty
start_entry = start_entry union with the element
remove element from the list
4.with the updated start_entry, traverse the list again until there is not new update
上面的算法应该返回连接图的顶点列表.然而,由于数据集大小,我遇到了运行时问题.有大约100000个条目.所以我只是想知道是否有人知道有更有效的方法来查找连接图.
数据结构也可以改为(如果这更容易)A,B B,C E,F ...每个条目代表图的边缘.
1> Peter de Riv..:
这看起来像是使用不相交集数据结构的理想情况.
这使您可以在几乎线性的时间内连接在一起.
示例Python代码
from collections import defaultdict
data=["A","B","C"],["C","D","E"],["F","G"]
# Prepare mapping from data element to index
S = {}
for a in data:
for x in a:
if x not in S:
S[x] = len(S)
N = len(S)
rank=[0]*N
parent=range(N)
def Find(x):
"""Find representative of connected component"""
if parent[x] != x:
parent[x] = Find(parent[x])
return parent[x]
def Union(x,y):
"""Merge sets containing elements x and y"""
x = Find(x)
y = Find(y)
if x == y:
return
if rank[x]rank[y]:
parent[y] = x
else:
parent[y] = x
rank[x] += 1
# Merge all sets
for a in data:
x = a[0]
for y in a[1:]:
Union(S[x],S[y])
# Report disconnected graphs
V=defaultdict(list)
for x in S:
V[Find(S[x])].append(x)
print V.values()
版画
[['A', 'C', 'B', 'E', 'D'], ['G', 'F']]