python - 在Python中查找与某个字符串相关的所有元组

Question

我正在尝试查找与字符串相关的所有元组，而不仅仅是与其匹配。这是我做的:

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可达的所有边。我怎样才能得到它们？

Answer 1

你的问题是找到connected component init 在由 edge list data structure 定义的无向图中.

这个数据结构对于这个问题用起来不是很方便，所以第一步是把它改造成一个adjacency list .从那里，我们可以应用任何标准 graph traversal算法，例如 depth first search .完成后，我们可以将结果转换回您希望用于输出的边列表格式。

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')]