python - 如何将迭代 DFS 变成递归 DFS？

Question

我通过实现堆栈编写了一个迭代 DFS。现在我试图递归地编写相同的 DFS，但我遇到了问题。

我的问题是，当我迭代编写它时，我可以保留某些全局变量，例如 paths=[] 并在找到新路径时添加到其中。

我对递归方法感到困惑的是，基本上我想跟踪两组结果:

1) 递归访问节点寻找新路径2) 每次我找到一条新路径时，我都想将其添加到一个路径列表中，然后返回该列表。

因此，我的递归函数现在被编写为在基本情况下返回单个路径，并在函数末尾返回路径列表。

什么是更好的写法？

此处可运行 Python 脚本:

https://ideone.com/ekfFDP

代码在这里:

graph = {'A': ['B', 'C'],
         'B': ['A', 'D', 'E'],
         'C': ['A', 'F'],
         'D': ['B'],
         'E': ['B', 'F'],
         'F': ['C', 'E'],
         'G': ['K']}


def push(array, item):
    array.insert(0, item)

def pop(array):
    return array.pop(0)

def dfs_paths(graph, start, goal):
    paths = []
    stack = [(start, [start])]

    while stack:
        (vertex, path) = pop(stack)
        vertices = graph[vertex]

        for next_vertex in (set(vertices) - set(path)):
            new_path = path + [next_vertex]

            if next_vertex == goal:
                paths.append(new_path)
            else:
                push(stack, (next_vertex, new_path))

    return paths

print dfs_paths(graph, 'A', 'F') # [['A', 'C', 'F'], ['A', 'B', 'E', 'F']]

def dfs_paths_rec(graph, start, goal, path=[]):
    if start == goal:
        path.append(start)
        return path

    paths = []
    for next in set(graph[start]) - set(path):
        new_path = dfs_paths_rec(graph, next, goal, path + [next])
        paths.append(new_path)

    return paths

print dfs_paths_rec(graph, 'A', 'F')

# [[[[[['C', 'A', 'B', 'E', 'F', 'F']], []]], ['C', 'F', 'F']], [[[['B', 'A', 'C', 'F', 'F']]], [['B', 'E', 'F', 'F']], []]]

Answer 1

要获得平面列表的结果，您需要使用 list.extend()而不是 list.append()。