尝试在Python中使用DFS递归在图形中查找所有路径 [英] trying to find all the path in a graph using DFS recursive in Python

问题描述

我找到了一段时间前发布的解决方案，并尝试将其应用于练习中，但无效。
我有一个具有结点和边的类图，以及一个给所有结点的所有子结点的childrenChild方法。所有这些都很好。这是我用于DFS搜索的代码，我想找到 all 路径：

I have found a solution that was posted some times ago and I have tried to apply it to my exercise but it doesn't work. I have a class graph that has nodes and edges and a method childrenOf that gives all the children of a node. All this works fine. This is my code for the DFS search and I want to find all the paths:

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，但没有成功。该图是成功创建的，因此并非来自此图。谢谢

I only got empty lists. WHere do I need to look at? When I was doing path=myDFS... in the loop I had at least the last path. I tried path+=myDFS without success. The graph was created with success so it doesn't come from it. Thanks

推荐答案

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

Since you only want to get all paths from start to end, the path is appended to your total path list when it reaches the end. The total list of paths is not returned but rather populated:

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)

这篇关于尝试在Python中使用DFS递归在图形中查找所有路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！