此代码在 python official essays on graph theory 中给出.这是代码:
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的关键是递归发生在路径累积之前。换句话说，在将任何内容放入“路径”列表之前，递归将进行到它需要进行的深度。在返回列表之前，所有最深的 sibling 都在“路径”上累积。
我相信代码使用“附加”而不是“扩展”是正确的，因为“路径”是所有路径的累加器。虽然它可能被写成
paths += find_all_paths(graph, node, end, path)
(编辑)...而不是
newpaths = find_all_paths(graph, node, end, path)
for newpath in newpaths:
paths.append(newpath)
关于python - 此 python 代码是否使用深度优先搜索 (DFS) 来查找所有路径？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4230878/