此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)