幅優先探索とは、全探索アルゴリズムの一種です。最短経路を求める際に使用される基本的なアルゴリズムです。木などのグラフやグラフと同一視できるものを探索する際に良く使われます。深さ優先探索と似ていますが、幅優先探索は始めの状態に近いものから順番に探索していきます。BFSと略されることも多いです。以下のような順番で探索していきます。BFSの状態遷移の順番アルゴリズム幅優先探索ではキューを用いることで以下のように探索することができます。始めの状態から遷移可能な状態を、全てキューに入れるキューに要素がなければ終了する現在の状態から遷移可能な状態を、全てキューに入れるキューから1つ要素を取り出し、そこに状態を遷移させる2.に戻る(キューではなくスタックで実装すると、深さ優先探索になります。)途中まで探索した時は以下のような状態になります。状態を変更するたびに、キューに遷移可能な場所の情報を入れておきます。※既に行ったことのある場所(上の図では0など)をキューに入れるようにすると無限ループになってしまうので気をつけましょう。具体例で試してみる例えば、以下のようなグラフについて考えます。「OK」、たどり着けなければ「NO」を返すプログラムを幅優先探索で実装します。隣接行列(グラフを参照のこと)を用いると以下のようになります。print("NO")出力は以下のようになります。隣接リスト表現(グラフを参照のこと)を用いると以下のようになります。0;}出力はPythonの例と同じです。問題概要R行C列の迷路が与えられる。考え方スタート地点から、幅優先探索によりゴールまでの最短距離を求めれば完了です。通った点について、スタート地点からの最短距離を記録していきましょう。迷路上での探索なので、先程のグラフの例と少し実装が異なりますが、基本となるアルゴリズムは変わりません。...キュー(Queue)・待ち行列キューは待ち行列とも呼ばれます。頂点(ノード)と、頂点同士の関係を表したデータ構造です。コメントをキャンセルメールアドレスが公開されることはありません。*次回のコメントで使用するためブラウザーに自分の名前、メールアドレス、サイトを保存する。上に表示された文字を入力してください。