python - Python での深さ優先検索

Question

Python で検索アルゴリズムを実装する際に問題があります。開始状態から終了状態へのパスを返すことができる汎用的な深さ優先検索コードが必要です。

Answer 1

Python でのグラフの実装に関するこのエッセイから始めて、DFS がスタックを使用してグラフのノードをポップインおよびポップアウトする可能性があることを理解してください。この考えがあれば、Python での DFS の実装を進めるのに役立つかもしれません。また、具体的な質問がある場合は、ここに投稿してください。喜んでお手伝いします。

Answer 2

literateprograms.org で詳細な実装の説明を見つけることができます。

（実際、これはほとんど最初の Google ヒットです。SO に質問を投稿する前に試してみると、次回に役立つかもしれません）

Answer 3

隣接リスト表現を使用してグラフを実装します。それを実装するコードは次のとおりです。(このコードは、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) 関数は必要ありません。次に、隣接リストの実装部分を取り除き、実際のトラバーサル部分を使用する必要があります。