Skip to main content
 首页 » 编程设计

python之如何将迭代 DFS 变成递归 DFS

2025年05月04日9jackei

我通过实现堆栈编写了一个迭代 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']], []]] 

请您参考如下方法:

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