这个Python代码是否使用深度优先搜索（DFS）来查找所有路径？

此代码在python official essays on graph theory中给出。这里的代码：这个Python代码是否使用深度优先搜索（DFS）来查找所有路径？

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图中的同胞概念相关联来解释代码？谢谢。

来源

2010-11-20 Pupil

'paths.extend（newpaths）' – 2010-11-20 02:25:59

作为参考，我总是会'不在图中开始而不是在'无图。 has_key（start）'（我假设'graph'是一个'dict'或类似的）。 – 2010-11-20 02:27:18

克里斯，是的'图'是一个'字典'。 – Pupil 2010-11-20 02:28:04

看到它是DFS的关键是递归发生在路径积累之前。换句话说，在将任何东西放在“路径”列表中之前，递归将尽可能地深入。在返回列表之前，所有最深的兄弟姐妹在“路径”上积累。

我相信代码是正确的“附加”而不是“扩展”，因为“路径”是所有路径的累加器。虽然它也许可以写成

paths += find_all_paths(graph, node, end, path)

（编辑）...而不是

newpaths = find_all_paths(graph, node, end, path) 
for newpath in newpaths: 
    paths.append(newpath)

来源

2010-11-20 03:03:52 mjhm

感谢mjhm的回答。你能告诉哪里包括你建议的'path + = find_all_paths（图形，节点，结束，路径）'这一行吗？ – Pupil 2010-11-20 03:18:45

是的，这个算法确实是一个DFS。请注意，它是如何在循环遍历各个节点时立即递归（进入孩子），而不是广度优先搜索，它基本上会生成一个可行节点列表（例如，所有在同一深度级别上的兄弟姐妹）当那些不符合您的要求时递归。

来源

2010-11-20 02:59:42 Stigma

考虑以下修改和执行脚本：

def find_all_paths(graph, start, end, path=[]): 
    path = path + [start] 
    print 'adding %d'%start 
    if start == end: 
     return [path] 
    if not graph.has_key(start): 
     return [] 
    paths = [] 
    for node in graph[start]: 
     if node not in path: 
      paths.extend(find_all_paths(graph, node, end, path)) 
    print 'returning ' + str(paths) 
    return paths 

G = {1:[2,3,4], 2:[1,4], 3:[1,4], 4:[1,2,3]} 
find_all_paths(G, 1, 4)

输出：

adding 1 
adding 2 
adding 4 
returning [[1, 2, 4]] 
adding 3 
adding 4 
returning [[1, 3, 4]] 
adding 4 
returning [[1, 2, 4], [1, 3, 4], [1, 4]]

注意如何在添加3之前返回第一个路径，并且在添加4之前返回第二个路径。

来源

2010-11-20 03:21:55

这个Python代码是否使用深度优先搜索（DFS）来查找所有路径？

回答

相关问题