深さ優先探索 - Algoful

深さ優先探索(Depth First Search)とは 深さ優先探索とは、木構造やグラフの探索を行うためのアルゴリズムです。始点となるノードから目的のノードが見つかるか子のないノードにたどり着くまで探索を繰り返し、そのあとは探索の終わってないノードまで戻って再度探索を繰り返します。 探索するのノードは スタック(FILO) を使って管理することになります。あるいは再帰的に呼び出す方法を用います。 アルゴリズム 始点のノードを探索待ちスタックに追加する。 探索待ちスタックにノードがあれば取り出す。なければ全ノード探索完了。 取り出したノードが目的ノードであれば探索完了。 取り出したノードに隣接するノードの内、未探索のノードを探索待ちスタックに追加する。 2. の処理にもどる。 先入れ後出しのスタックに探索待ちのノードを格納することで、始点から末端のノードまでの探索が一直線に行われることにな

[lazy24day]

“Path”