您的问题是要找到连接成分的
init在由所定义的无向图边缘列表数据结构。
此数据结构对于解决此问题不是很方便，因此第一步是将其转换为邻接表。从那里，我们可以应用任何标准的图形遍历算法，例如深度优先搜索。完成后，我们可以将结果转换回想要输出的边列表格式。
from collections import defaultdictdef 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')]
