Python:跟随 "path"的元组？

Question

短版:
是)我有的:
2 元组列表，例如 [("a", "b"), ("b", "c"), ("d", "e"), ("c", "d"), ("f", "g")]不一定按字母顺序排列

我想要的是:
给出一个开始字母(比如“a”)和一个结束字母(比如“e”)我希望 Python 从上面的列表中找到可用的 2 元组列表，它将开始字母“链接”到结束字母，所以在本例中，该列表将是 [("a", "b"), ("b", "c"), ("c", "d"), ("d", "e")]按此顺序(a --> b --> c --> d --> e)
加长版:
大家好，这是我在 SO 上的第一篇文章，尽管我已经浏览了很长时间并且总是在这里找到我的答案，很棒的社区!

我的工作要做一些数据分析，并且我有一定数量的数据集(为简单起见，我将在这里用字母表示)，我只知道数学上的区别:(“a” - “b”)， (“b” - “c”)等(这些是我的输入)。我将用 2 元组表示这些输入。这个想法是计算数据集“a”和“e”之间的差异，即“a” - “e”，在这种情况下可以通过对一些中间数据集差异(我的输入)求和来获得:(“a”-“b”)+(“b”-“c”)+(“c”-“d”)+(“d”-“e”)=“a”-“e”。

我想知道是否有一个 Python 模块可以完成我想要的工作，或者是否有一种使用 Python 语法的简单方法来做到这一点。在上面的简单情况下，每个字母仅出现在列表中的 2 个元组中，但在一般情况下，可能会有一个包含正确字母的额外元组，但不允许将开始字母链接到结束字母(例如如果有一个额外的元组(“b”，“h”)，它将在代码的第一次迭代中与元组(“b”，“c”)一起找到，但它应该被丢弃，因为字母“h”不会“引导”任何地方)。我在处理此类案件时遇到了麻烦。

我希望问题足够清楚，很难用简单的话来表达。

提前致谢!

Answer 1

看起来这里的方法是使用一些图形分析工具来找到 shortest path一对节点之间。尽管这种情况实际上在某种程度上简化了问题，因为您提到每个字母仅出现在列表中的 2 个元组上，这意味着只有一条路径连接一对节点。虽然常见的场景是有多个可能的路径连接源节点和目标节点，但在这种情况下，我们需要一些算法来找到其中最短的路径。

所以解决这个问题的方法是使用 NetworkX构建一个图，让元组列表表示图的边缘，并查找 nx.shortest_path 一对source之间和 target节点:

import networkx as nx

edges = [("a", "b"), ("b", "c"), ("d", "e"), ("c", "d"), ("f", "g")]

G = nx.from_edgelist(edges)
path_nodes = nx.shortest_path(G, 'a', 'e')
# ['a', 'b', 'c', 'd', 'e']

如果您希望将输出作为元组列表，您可以轻松地执行以下操作:

list(zip(path_nodes[:-1], path_nodes[1:]))
# [('a', 'b'), ('b', 'c'), ('c', 'd'), ('d', 'e')]

请注意，这里的顺序不是一个相关因素，感觉这基本上只是从提供的边定义了一个图， shortest_path将只寻找连接源节点和目标节点所需的最小图边。