Python：遵循元组的“路径”？

Question

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

我想要什么： 给出一个开始字母（比如“a”）和一个结束字母（比如“e”）我希望 Python 从上面的列表中找到可用的 2-tuples 列表，它可以“链接”开始字母到结尾字母，因此在本例中，该列表将按[("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

看起来这里的方法是使用一些图形分析工具来找到一对节点之间的最短路径。尽管这种情况实际上是对问题的某种简化，因为您提到每个字母仅出现在 list 中的 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只会寻找连接源节点和目标节点所需的最小图边。