python - Python中的深度优先搜索

Question

我在用 Python 实现搜索算法时遇到问题。我需要一个通用的深度优先搜索代码，它可以返回从开始状态到结束状态的路径。

Answer 1

从这篇关于在 Python 中实现图的文章开始，然后了解 DFS 可能使用堆栈来弹出和弹出图的节点。有了这个想法可能会帮助您继续在 Python 中实现 DFS。如果您有具体问题，请在此处发布，人们随时准备提供帮助。

Answer 2

您可以在 literateprograms.org找到详细的实现说明。

（实际上，这几乎是谷歌的第一个热门，在下次发布关于 SO 的问题之前尝试一下可能会有所帮助）

Answer 3

使用邻接表表示来实现图。实现它的代码如下。（如果您使用 Python 读取图形上的文本文件并实现邻接列表，则此代码是特定的）

（Python 3.3）

def ajlist(nameofgraph,start,goal):

x=input("enter the name of the file you want to implement adjecency list: ")##file.txt##
text_file=open(x,"r")
nameofgraph={}##use a dictionary##
for line in text_file:
   (vertex,val)=line.split()
   if vertex not in nameofgraph:
      nameofgraph[vertex]=set9[val])
   else:
      nameofgraph.get[key].add(val)
stack=[(stack,[start])]
while stack:
   (vertex,path)=stack.pop()
   for next in graph[vertex]-set(path):
      if next==goal:
         yield (path+[next])
      else:
         stack.append((next,path+[next]))

当你想运行这个使用这个语法list(DFS(nameofgraph,start,goal))

以上是进行 DFS 并在图中找到路径的最简单方法。如果你已经在 python 中实现了一个图形，那么你不需要 (input) 函数。然后你要做的就是去掉实现邻接列表部分并使用真正的遍历部分。