我试图找到与字符串相关的所有元组,而不仅仅是与之匹配的元组。 这是我做的:
from itertools import chain
data = [('A','B'),('B','C'),('B','D'),('B','F'),('F','W'),('W','H'),('G','Z')]
init = 'A'
filtered_init = [item for item in data if item[0] == init or item[1] == init]
elements = list(dict.fromkeys([ i for i in chain(*filtered_init)]))
elements.remove(init)
dat = []
for i in elements:
sync = [item for item in data if item[0] == i or item[1] == i]
dat.append(sync)
print(dat)
结果是:
[('A', 'B'), ('B', 'C'), ('B', 'D'), ('B', 'F')]
但是,它只包含与A-B相关的级别。
我想找到的是与init
字符串相关的所有元组,如下图所示:
换句话说,[('A','B'),('B','C'),('B','D'),('B','F'),('F','W'),('W','H')]
它是找到所有的边可以到达init
。
我怎样才能得到它们?你知道吗
为了提高效率,可以使用DSU。此解决方案适用于O(N)
输出:[('A','B'),('B','C'),('B','D'),('B','F'),('F','W'),('W','H')]
您的问题是在由edge list data structure定义的无向图中找到
init
的connected component。你知道吗对于这个问题,使用这个数据结构不是很方便,所以第一步是将它转换成adjacency list。从那里,我们可以应用任何标准的graph traversal算法,比如depth first search。完成后,我们可以将结果转换回您想要的输出边缘列表格式。你知道吗
用法:
一个非常幼稚的解决方案,对于复杂的树可能不太有效。你知道吗
相关问题 更多 >
编程相关推荐