深度优先搜索以在图中查找路径

Question

我试图在 Python 中使用深度优先搜索在图中找到两点之间的路径。这个想法是 return 从点 a 到点 b 的路径（不一定是最短的）或者如果路径不存在则为空列表。我有一个 class ，它包含一个邻接列表（称为图的字典），一个访问节点的字典和一个堆栈（一个称为路径的列表）来跟踪当前路径。我用来执行此操作的递归函数是一个名为 getPath(self,a,b) 的方法。我遇到的问题是，一旦找到目标节点，我就无法 return 堆栈，我认为是因为堆栈只是 returned 作为递归调用的一部分并且函数继续运行。我可以改变什么来完成这项工作？代码如下：

def getPath(self,a,b):
        self.visited["{}".format(a)]=1 #mark a as visited
        self.path.append("{}".format(a)) #add a to current path
        if ("{}".format(a)=="{}".format(b)): #check to see if we've reached our destination
            return self.path #here is where I would like the function to return the path
        else:
            for v in self.graph["{}".format(a)]:
                if self.visited[v]==0:
                    self.getPath(v,b)
            self.path.pop #remove v from our current path if we only find dead ends from its edges

Answer 1

在上述 else 块中的代码中，您 return 对递归调用一无所获。

那么，如果 children 调用：

self.getPath(v,b)

returns self.path 但在该函数的 parent 调用中 return 什么都没有。

因此，您必须在 else 块中进行一些更改以跟踪这些 return 值。

def getPath(self,a,b):
        self.visited["{}".format(a)]=1 #mark a as visited
        self.path.append("{}".format(a)) #add a to current path
        if ("{}".format(a)=="{}".format(b)): #check to see if we've reached our destination
            return self.path #here is where I would like the function to return the path
        else:
            for v in self.graph["{}".format(a)]:
                if self.visited[v]==0:
                    result = self.getPath(v,b)
                    if(result != None):
                        return result
            self.path.pop #remove v from our current path if we only find dead ends from its edges
            return None

深度优先搜索以在图中查找路径

Depth first search to find path in graph

python

algorithm

recursion

graph

depth-first-search