不指定终点节点，查找所有路径？

Question

我正在尝试进行深度优先搜索以查找所有路径的列表，然后确定最短和最长的路径。

Python文档(https://www.python.org/doc/essays/graphs/)中提到了以下内容，需要一个结束节点：

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 

我的问题是如何在（有向无环）图中找到所有路径，而不需要指定结束节点？我的起始节点始终保持不变。

我可以在开始时使用for循环来迭代节点。但这似乎不是最有效的方法，因为我可能会使用相同的路径重新访问一个节点，这将浪费计算时间。

for node in nodeList:
    find_all_paths(graph, 0, node) 

- ForeverLearning

Answer 1

您的深度优先搜索代码可以通过简单地修改来查找到所有终节点的所有路径。

首先，删除 end 参数和 start == end 的基本情况。然后，在开始递归步骤之前，只需将 path 添加到 paths 中即可。在递归调用中不再尝试传递 end。

就是这样:

def find_all_paths(graph, start, path=[]):
    path = path + [start]
    if not graph.has_key(start):
        return [path]
    paths = [path]
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_paths(graph, node, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths

请注意，您可以使用递归生成器更高效地完成此操作，而不是构建一个大型路径列表（我还修改了对于不在图形中的节点的特殊检查：使用not in运算符比使用dict.has_key更好）：

def find_all_paths(graph, start, path=[]):
    path = path + [start]
    yield path
    if start not in graph:
        return
    for node in graph[start]:
        if node not in path:
            yield from find_all_paths(graph, node, path)

请注意，yield from 仅适用于 Python 3.3 及更高版本。如果您使用的是早期版本，请使用显式循环：

for newpath in find_all_paths(graph, node, path):
    yield newpath

- Blckknght