跨递归迭代构建集合

Question

我正在尝试使用 Python 实现 this question's top answer 中描述的“所有路径”算法。

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

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 和节点 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]]

我希望这至少是您要找的东西。

跨递归迭代构建集合

Building a collection across recursive iterations

python

recursion

graph

nodes