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

问题内容：

我试图找到与字符串相关的所有元组，而不仅仅是与其匹配。这是我做的：

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

但是，它仅包含AB相关级别。我要查找的是与init字符串相关的所有元组，如下图所示：

换句话说，[('A','B'),('B','C'),('B','D'),('B','F'),('F','W'),('W','H')]
它是找到可以到达的所有边init。我怎样才能得到它们？

问题答案：

您的问题是要找到连接成分的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')]

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

微信关注