这是否Python代码采用深度优先搜索（DFS）寻找所有的路径？

Question

这个代码在图论 蟒正式论文给出。下面的代码：

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

我不擅长蟒蛇，因为我还没有练习过，并在其中阅读足够了。能否请您通过这有关在DFS图中的孩子，兄弟姐妹的概念解释的代码？感谢。

Answer 1

要看到，这是一个DFS的关键是递归的路径的累积之前发生。换句话说，因为它需要放置任何东西，“路径”名单之前去递归会去深。所有最深兄妹返回列表之前被累积的“路径”。

相信代码是与“追加”正确而不是“延伸”，因为“路径”是所有路径的累加器。虽然它很可能被写为

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

（编辑）...而不是

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

Answer 2

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

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之前返回第二路径。

Answer 3

是，该算法确实是一个DFS。注意它是如何递归马上遍历各个节点时（进入孩子），而不是广度优先搜索它们基本上将使得可行的节点列表（例如，在深度同级别的一切，又名兄弟姐妹），只有递归时那些不符合您的要求。