将值附加到递归方法中的列表

Question

我正在尝试

    def DFSUtil(self, u, d, visited, path):
    visited = []
    u.visited = True
    visited.append(u)
    path.append(u)
    all_adjacent_vertices = []
    for e in u.edges:
        all_adjacent_vertices.append(self.opposite(e, u))

    if u == d:
       return path


    else:
        for i in all_adjacent_vertices:
            if i not in visited and i.visited == False:
                self.DFSUtil(i, d, visited, path)

    path.pop()
    u.visited = False
    return path

def DFS(self, start, end):
    visited = []
    path = []
    x = self.DFSUtil(start, end, visited, path)

我正在尝试从我的递归函数中获取从STARTING NODE U到ENDING NODE D的路径列表，但是，在每次递归调用期间，它都被覆盖，并且我无法再访问它。谁能指出我如何解决这个问题。

我想将所有路径添加到一个名为AllPossiblePaths的单独列表中，从本质上创建一个列表列表。

Answer 1

基本上，将结果列表传递到递归函数中。当您击中没有邻居的节点时，将当前路径的副本添加到结果列表中并返回。

可以通过多种方式简化代码，但是这是一个最小的完整示例，您可以根据自己的图形结构进行调整：

def all_paths(node, graph, path=[], visited=set(), paths=[]):
    if node in visited:
        return paths

    visited.add(node)
    path.append(node)

    if not graph[node]:
        paths.append(path[:])

    for neighbor in graph[node]:
        all_paths(neighbor, graph, path, visited, paths)

    path.pop()
    visited.remove(node)
    return paths

if __name__ == "__main__":
    graph = {
        "a": ["b", "c", "d"],
        "b": ["d"],
        "c": ["e"],
        "d": ["c"],
        "e": []
    }
    """
    +---d <--+
    |   ^    |
    |   |    |
    |   a -> b
    |   |
    |   v
    +-> c -> e
    """
    for path in all_paths("a", graph):
        print(path)

输出：

['a', 'b', 'd', 'c', 'e']
['a', 'c', 'e']
['a', 'd', 'c', 'e']