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

Question

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

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

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

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

所以我的递归函数现在被编写成 returns 基本情况下的单个路径，并且 returns 函数末尾的路径列表。

什么是更好的写法？

可运行 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()。

Answer 2

尝试这样的事情：

def all_paths_dfs(graph, start, end, path=None):
    if path is None:
        path = []

    path.append(start)
    all_paths = set()

    if start == end:
        all_paths.add(tuple(path))
    else:
        for neighbor in graph[start]:
            if neighbor not in path:
                all_paths |= all_paths_dfs(graph, neighbor, end, path)

    path.pop()
    return all_paths


if __name__ == "__main__":
    graph = {'A': {'B', 'C'},
             'B': {'A', 'D', 'E'},
             'C': {'A', 'F'},
             'D': {'B'},
             'E': {'B', 'F'},
             'F': {'C', 'E'},
             'G': {'K'}}

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

哪个returns:

set([('A', 'C', 'F'), ('A', 'B', 'E', 'F')])

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

How to turn a iterative DFS into a recursive DFS?

python

recursion

depth-first-search

可运行 Python 脚本在这里：

代码在这里：