此python代码是否使用深度优先搜索(DFS)来查找所有路径?
问题内容:
该代码在有关图论的python官方论文中给出。这是代码:
def find_all_paths(graph, start, end, path=[]):
path = path + [start]
if start == end:
return [path]
if not graph.has_key(start):
return []
paths = []
for node in graph[start]:
if node not in path:
newpaths = find_all_paths(graph, node, end, path)
for newpath in newpaths:
paths.append(newpath)
return paths
我不擅长python,因为我还没有足够的实践能力和阅读能力。您能否通过将其与DFS图中的兄弟姐妹概念相关联来解释代码?谢谢。
问题答案:
看到它是DFS的关键是递归发生在路径积累之前。换句话说,在将任何内容放入“路径”列表之前,递归将进行所需的深度。返回列表之前,所有最深的兄弟姐妹都累积在“路径”上。
我相信代码的正确之处在于“追加”而不是“扩展”,因为“路径”是所有路径的累加器。虽然它可能写成
paths += find_all_paths(graph, node, end, path)
(编辑)…而不是
newpaths = find_all_paths(graph, node, end, path)
for newpath in newpaths:
paths.append(newpath)