Skip to main content
 首页 » 编程设计

python之在不指定结束节点的情况下查找所有路径

2025年05月04日14over140

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

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)  

请您参考如下方法:

您的深度优先搜索代码只需稍作调整即可找到所有端节点的所有路径。

首先,删除 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