Search)とは深さ優先探索とは、木構造やグラフの探索を行うためのアルゴリズムです。始点となるノードから目的のノードが見つかるか子のないノードにたどり着くまで探索を繰り返し、そのあとは探索の終わってないノードまで戻って再度探索を繰り返します。使って管理することになります。再帰的に呼び出す方法を用います。アルゴリズム始点のノードを探索待ちスタックに追加する。探索待ちスタックにノードがあれば取り出す。なければ全ノード探索完了。取り出したノードが目的ノードであれば探索完了。取り出したノードに隣接するノードの内、未探索のノードを探索待ちスタックに追加する。先入れ後出しのスタックに探索待ちのノードを格納することで、始点から末端のノードまでの探索が一直線に行われることになります。あとは探しているノードが見つかるか、スタックが空になるまで繰り返すだけです。幅優先探索と比べての違いは、キューを使うかスタックを使うかの違いと言っても過言ではありません。迷路を解く深さ優先探索の例として迷路を解いてみます。迷路もグラフの一つとみなせるので、深さ優先探索で答えを見つけることができます。答えが求まれば、スタート地点からゴール地点までの経路を求めることができます。迷路生成アルゴリズム(穴掘り法)で生成した迷路を解くこととします。迷路は一意のルートでゴールに辿り着きます。ゴールまでの経路は最短経路でもあります。スタート初めてからゴールを見つけるだけなら上記のアルゴリズムを実装すればよいですが、経路保持するには少し工夫が必要です。経路の保存方法ノードを探索するときに、どのノードから到達したかという情報(直前のノード)を保持します。ノードは1回しか探索されないので、そのノードへの到達経路は1つのみです。したがって、ゴールのノードから直前のノードを逆にたどっていけばスタートのノードへの経路が求まります。詳しくはサンプルコードを参照してください。動作確認用迷路の配列を作成します。console.log('ゴールが見つかりました。