「深さ優先探索」の版間の差分
削除された内容 追加された内容
編集の要約なし |
|||
29行目:
このグラフでは深さを増やしていくたびに、アルゴリズムが探索を断念して他の枝に行くまで"ABFE", "AEFB"のループが長くなる。
== 擬似コード
=== 再帰あり ===
深さ優先探索(v)
v に訪問済みの印を付ける
36 ⟶ 37行目:
深さ優先探索(i)
===
深さ優先探索(v)
S ← 空のスタック
v に訪問済みの印を付ける
v を S に積む
while (S が空ではない)
v ← S から取り出す
v を処理する
for each (v に接続していて かつ 未訪問の頂点 i)
i に訪問済みの印を付ける
i を S に積む
== Pythonでの実装(再帰なし) ==
以下は、2頂点間の経路を探す例。なお、これを[[幅優先探索]]でやると、辺の重みなしの[[最短経路問題]]になる。
'''def''' depthFirstSearch( start, goal ):
stack = Stack()
45 ⟶ 58行目:
node = stack.top()
'''if''' node == goal:
'''return''' stack # stack
'''else''':
child = node.findUnvisitedChild()
53 ⟶ 66行目:
child.setVisited()
stack.push( child )
== 関連項目 ==
86 ⟶ 76行目:
{{デフォルトソート:ふかさゆうせんたんさく}}
[[Category:検索アルゴリズム]]
[[Category:組合せ最適化]]
|