尝试在 Python 中使用 DFS 递归查找图中的所有路径

Question

我找到了一个前几次发布的解决方案，我试图将它应用到我的练习中，但它不起作用。我有一个包含节点和边的类图和一个提供节点的所有子节点的方法 childrenOf。所有这些工作正常。这是我的 DFS 搜索代码，我想找到所有路径：

def myDFS(graph,start,end,path=[]):
path=path+[start]
if start==end:
    return path
paths=[]
for node in graph.childrenOf(start):
    if node not in path:
        paths.extend(myDFS(graph,node,end,path))            
return paths

我只有空列表。我需要看哪里？当我在循环中执行 path=myDFS... 时，我至少有最后一条路径。我试过 path+=myDFS 没有成功。该图是成功创建的，因此它不是来自它。谢谢

Answer 1

由于您只想获取从头到尾的所有路径，因此该路径在到达末尾时会附加到您的总路径列表中。不返回路径的总列表而是填充：

paths = []

def myDFS(graph,start,end,path=[]): 
    path=path+[start] 
    if start==end:
        paths.append(path) 
    for node in graph.childrenOf(start):
        if node not in path:
            myDFS(graph,node,end,path)