此python代码是否使用深度优先搜索（DFS）来查找所有路径？ [英] Does this python code employs Depth First Search (DFS) for finding all paths?

问题描述

此代码在关于图论的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图中的兄弟姐妹概念相关联来解释代码？谢谢。

I am not adept at python as I haven't yet had enough of practicing and reading in it. Can you please explain the code by relating this to the child-sibling concept in DFS diagram? Thanks.

推荐答案

看到它是DFS的关键是递归发生在路径积累之前。换句话说，在将任何内容放入路径列表之前，递归将进行所需的深度。返回列表之前，所有最深的兄弟姐妹都存储在路径上。

The key to seeing that it is a DFS is that the recursion happens before the accumulation of paths. In other words the recursion will go as deep as it needs to go before putting anything on the "paths" list. All the deepest siblings are accumulated on "paths" before returning the list.

我认为代码的正确之处在于追加而不是扩展，因为路径 是所有路径的累加器。虽然它可能写成

I believe the code is correct with the "append" rather than "extend", since "paths" is the accumulator of all paths. Though it could probably be written as

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

（edit）...而不是

(edit) ...instead of

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

这篇关于此python代码是否使用深度优先搜索（DFS）来查找所有路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！