我通过实现堆栈编写了一个迭代 DFS。现在我试图递归地编写相同的 DFS,但我遇到了问题。
我的问题是,当我迭代编写它时,我可以保留某些全局变量,例如 paths=[] 并在找到新路径时添加到其中。
我对递归方法感到困惑的是,基本上我想跟踪两组结果:
1) 递归访问节点寻找新路径 2) 每次我找到一条新路径时,我都想将其添加到一个路径列表中,然后返回该列表。
因此,我的递归函数现在被编写为在基本情况下返回单个路径,并在函数末尾返回路径列表。
什么是更好的写法?
此处可运行 Python 脚本:
代码在这里:
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()。
