您的问题是要找到连接成分的init
在由所定义的无向图边缘列表数据结构。
此数据结构对于解决此问题不是很方便,因此第一步是将其转换为邻接表。从那里,我们可以应用任何标准的图形遍历算法,例如深度优先搜索。完成后,我们可以将结果转换回想要输出的边列表格式。
from collections import defaultdict
def find_connected_component(edge_list, start):
# convert to adjacency list
edges = defaultdict(list)
for a, b in edge_list:
edges[a].append(b)
edges[b].append(a)
# depth-first search
stack = [start]
seen = set()
while stack:
node = stack.pop()
if node not in seen:
seen.add(node)
stack.extend(edges[node])
# convert back to edge list
return [ edge for edge in edge_list if edge[0] in seen ]
用法:
>>> find_connected_component(data, init)
[('A', 'B'), ('B', 'C'), ('B', 'D'), ('B', 'F'), ('F', 'W'), ('W', 'H')]