查找与Python中某个字符串相关的所有元组 [英] Find all tuples related to a certain string in Python

问题描述

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

I am trying to find all tuples related to a string, not just matched to it. Here is what I made:

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字符串相关的所有元组，如下图所示:

However, it only contains A-B-related level. What I want to find is all tuples related to init string as described in the picture below:

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

In other words, [('A','B'),('B','C'),('B','D'),('B','F'),('F','W'),('W','H')] It is to find all edges reachable to init. How can I get them?

推荐答案

您的问题是找到边缘列表数据结构定义的无向图中/a>.

Your problem is to find the connected component of init in an undirected graph defined by an edge list data structure.

此数据结构不适用于此问题，因此第一步是将其转换为图形遍历算法，例如

This data structure is not very convenient to use for this problem, so the first step is to transform it into an adjacency list. From there, we can apply any standard graph traversal algorithm, such as depth first search. Once we're done, we can transform the result back into the edge list format you want for your output.

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中某个字符串相关的所有元组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！