2

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

4

3 回答 3

4

看到它是 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-20T03:03:52.943 回答
4

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

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-20T03:21:55.630 回答
1

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

于 2010-11-20T02:59:42.193 回答