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