跨递归迭代构建集合

Question

我正在尝试实现一个；所有路径"；这个问题的顶部答案中描述的算法使用Python。

到目前为止，我已经将函数定义为：

def AllPaths(start, end, edges):
print(start)
if (start == end):
return
for i in range(0, len(edges)):
if edges[i][1] == start:
AllPaths(edges[i][0], end, edges)

我加入了print(start)，试图让自己了解函数的行为。例如，如果初始函数调用是这样的：

edges = [ (1, 2), (1, 3), (2, 3), (3, 4) ]
AllPaths(edges[len(edges) - 1][1], edges[0][0], edges)

起始节点为4，结束节点为1，函数的输出为：

4
3
1
2
1

在输出的某个地方，它告诉我节点4和节点1之间的所有路径都包括：

[ (4, 3), (3, 1) ]
[ (4, 3), (3, 2), (2, 1) ]

但是，我如何在执行期间形成这些集合？如果我想跟踪有多少不同的路径，在执行期间如何计算这些路径？

Answer 1

如果你不介意我不遵循向后遍历路线，我觉得这很奇怪，那么这里有一个关于如何修改函数以查看发生了什么的建议：

def all_paths(start, end, edges):
if start == end:
return [[end]]
paths = []
for edge in edges:
if edge[0] == start:
paths += [[start] + path
for path in all_paths(edge[1], end, edges)]
return paths

edges = [(1, 2), (1, 3), (2, 3), (3, 4)]和start = 1; end = 4的输出：

[[1, 2, 3, 4],
[1, 3, 4]]

如果你想要一个直接的边缘结果，那么我建议：

def all_paths(start, end, edges):
paths = []
for edge in edges:
if edge[0] == start:
if edge[1] == end:
return [[edge]]
else:
paths += [[edge] + path
for path in all_paths(edge[1], end, edges)]
return paths

相同输入的输出：

[[(1, 2), (2, 3), (3, 4)],
[(1, 3), (3, 4)]]

但警告：如果图中有循环，例如edges = [(1, 2), (1, 3), (3, 1), (2, 3), (3, 4)]，那么这些算法将崩溃(递归不会停止(。在这些情况下，类似

def all_paths(start, end, edges):
edges = set(edges)
paths = []
for edge in edges:
if edge[0] == start:
if edge[1] == end:
paths += [[start, end]]
else:
new_edges = edges.difference({edge})
paths += [[start] + path
for path in all_paths(edge[1], end, new_edges)]
return paths

去除访问的边缘更好。start = 1; end = 4:的结果

[[1, 2, 3, 1, 3, 4],
[1, 2, 3, 4],
[1, 3, 1, 2, 3, 4],
[1, 3, 4]]

我希望这至少是你想要的一点点。