从元组列表生成所有可能的路径

Question

给定一个元组列表，需要从这个列表中找到所有唯一的路径：

输入：[('a','b'),('b','c'),('c','d'),('g','i'),('d','e'),('e','f'),('f','g'),('c','g')] 输出：[['a','b','c','d','e','f','g'],['a','b','c','g','i']]（两条唯一路径）

两个元组可以连接起来，如果一个元组的第二个元素与另一个元组的第一个元素匹配，即：一个元组是(_,a)，另一个元组是像(a,_)。

此问题已经在这里提出：Getting Unique Paths from list of tuple，但解决方案是使用Haskell实现的（而我对这种语言一无所知）。

但是您是否知道在Python中有没有有效的方法来解决这个问题？我知道库itertools有许多有效的内置函数可用于处理这样的问题，但我并不太熟悉它。

- Roulio

---

你尝试过什么来解决它？ - Devesh Kumar Singh

可能是从边列表构建所有哈密顿路径的副本。 - jennifer lawrence

Answer 1

你想要在图中找到所有的简单路径。

Python有一个非常出色的图处理库：networkx。你可以用只有几行代码的方式解决你的问题：

import networkx as nx

a = [('a','b'),('b','c'),('c','d'),('g','i'),('d','e'),('e','f'),('f','g'),('c','g')]

# Create graph
G = nx.Graph()
# Fill graph with data
G.add_edges_from(a)

# Get all simple paths from node 'a' to node 'i'
list(nx.all_simple_paths(G, 'a', 'i'))

将返回：

[['a', 'b', 'c', 'g', 'i'], ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'i']]

---

如果你想获得所有可能的路径，只需将最后一行替换即可：

for start in G.nodes:
    for end in G.nodes:
        if start != end:
            print(list(nx.all_simple_paths(G, start, end)))

- vurmux

---

非常感谢 :) 但是在你的解决方案中，你假设'a'和'i'一定是你可能路径的开头和结尾（在我的问题中，我没有假设路径如何开始和结束，我只知道它们应该如何构建）。但我想我可以通过简单地生成所有（起始/结束）组合，然后对每个组合应用你的方法来生成所有可能的路径（虽然可能会很长）。 - Roulio

更新了答案。 - vurmux

请注意，更新后的答案通过在所有节点上进行嵌套循环并调用nx.all_simple_paths将解决方案的平均时间复杂度变为*O(n ^ 3)*。 - blhsing

Answer 2

你可以构建一个字典，将每个父节点映射到相应的子节点列表，这样你就可以以平均时间复杂度O(n)递归地生成每个父节点的路径：

def get_paths(parent, mapping):
    if parent not in mapping:
        yield [parent]
        return
    for child in mapping[parent]:
        for path in get_paths(child, mapping):
            yield [parent, *path]

edges = [('a','b'),('b','c'),('c','d'),('g','i'),('d','e'),('e','f'),('f','g'),('c','g')]
parents = set()
children = set()
mapping = {}
for a, b in edges:
    mapping.setdefault(a, []).append(b)
    parents.add(a)
    children.add(b)
print([path for parent in parents - children for path in get_paths(parent, mapping)])

这将输出以下内容：

[['a', 'b', 'c', 'd', 'e', 'f', 'g', 'i'], ['a', 'b', 'c', 'g', 'i']]

- blhsing

Answer 3

你可以在生成器中使用递归：

d = [('a','b'),('b','c'),('c','d'),('g','i'),('d','e'),('e','f'),('f','g'),('c','g')]
def get_paths(start, c = []):
   r = [b for a, b in d if a == start]
   if r:
     for i in r:
        yield from get_paths(i, c+[i])
   else:
     yield c

print(list(get_paths('a', ['a'])))

输出：

[['a', 'b', 'c', 'd', 'e', 'f', 'g', 'i'], ['a', 'b', 'c', 'g', 'i']]

- Ajax1234

---

请注意，在每个递归调用中必须遍历所有节点，使得该解决方案的平均时间复杂度为O(n ^ 2)。它还需要预先知道起始节点，而这并没有作为此问题的输入给出。 - blhsing

@blhsing，你是如何得出我们答案的O(n^2)和O(n)的？你的字典查找是O(n)，但是在一个for循环中使用递归调用，最坏情况下的结果是>= O(2^n)（对于我的情况也是如此）。 - Ajax1234

字典查找平均成本为*O(1)，而在所有节点中线性搜索给定父节点的方法[b for a, b in d if a == start]成本为O(n)。递归调用会线性遍历所有节点，因此我的解决方案成本为O(n)，而你的成本为O(n ^ 2)。然而，另一个因素是分岔路径的数量，当父节点有多个子节点时会发生这种情况，如果该数字很大，则我的解决方案成本为O(n x m)，而你的成本则为O(n ^ 2 x m)*，其中n是节点数，m是分岔路径数。 - blhsing

我的回答包含了对d的额外遍历，但由于递归调用的线性时间复杂度，结果是不是为O(n)+O(n) => O(n)？循环体外的额外线性遍历不增加n的影响力。 - Ajax1234

不，你在每个递归调用中都迭代了所有节点的长度，而且递归调用至少要进行与节点数相同次数的操作，因此结果是n乘以n步。在字典中查找节点可以消除在每个递归调用中迭代所有节点的需要，因此我的解决方案具有*O(n)*复杂度。 - blhsing