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

Question

这段代码来自于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）图中的兄弟姐妹概念联系起来解释一下？谢谢。

Answer 1

是的，这个算法确实是深度优先搜索（DFS）。注意，当它遍历不同的节点时，会立刻进入子节点进行递归，这和广度优先搜索（BFS）不一样。广度优先搜索会先列出所有可以访问的节点，比如同一层级的节点（也就是兄弟节点），然后只有在这些节点不符合要求时才会进行递归。

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），关键在于递归发生在路径累积之前。换句话说，递归会一直深入，直到需要的深度，然后才会把任何东西放到“路径”列表里。在返回列表之前，所有最深的兄弟节点都会被累积到“路径”中。

我认为代码使用“append”是正确的，而不是“extend”，因为“路径”是所有路径的累积器。不过，它可能也可以写成

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

（编辑）...而不是

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