找到没有指定结束节点的所有路径？

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) 

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