幅優先探索とは
幅優先探索（はばゆうせんたんさく）とは、グラフや木構造といったデータ構造のすべての要素を調べる（探索する）ための代表的なアルゴリズムの一つです。英語の「Breadth-First Search」の頭文字をとって「BFS」とも呼ばれます。この探索法の特徴は、出発地点に近い階層から順番に、横方向（同じ深さの要素）をすべて調べ尽くしてから、次の深い階層へと進んでいくことです。スタート地点からの距離が近い順に調べていくため、最短経路（最も少ないステップ数でのゴール）を見つける問題に非常に適しています。実装には「キュー（Queue）」という先入れ先出しのデータ構造がよく使われます。
具体例
迷路のスタート地点からゴール地点までの最短ルートを探す場面を想定します。幅優先探索では、スタートから1歩で行けるすべてのマスを調べ、次に2歩で行けるすべてのマスを調べ、というように波紋が広がるように探索を進めます。これにより、最初に見つかったゴールへの経路が必ず最短のルートになります。
もう少し詳しく
幅優先探索の仕組みを理解する上で重要なのが、「キュー（Queue）」というデータ構造の役割です。キューは、レジの順番待ちの列のように、「先に入れたものから先に取り出す（FIFO：First In, First Out）」性質を持ちます。幅優先探索のプログラムでは、まず現在いる場所から1歩で行ける新しい場所をすべてキューの最後尾に追加します。そして、キューの先頭から順番に場所を取り出し、さらにそこから1歩で行ける場所をまた最後尾に追加していく、という処理を繰り返します。この「古いものから順に処理する」というキューの性質によって、必然的にスタート地点から近い場所から順番に探索が行われるよう制御されています。グラフ全体をくまなく調べることができる確実な方法ですが、未探索の場所をすべてキューに保持しておく必要があるため、巨大なグラフや複雑な木構造を探索する場合には、大量のメモリを消費してしまう（空間計算量が大きくなる）という弱点もあります。
試験でのポイント
試験対策として最も重要なのは、「幅優先探索＝キュー（Queue）を使う」という対応関係を条件反射で思い出せるようにすることです。これは基本情報技術者試験などで非常によく出題される鉄板の知識です。また、別の探索手法である深さ優先探索との比較も頻出します。幅優先探索は「浅いところから広く探す」「最短経路を見つけるのに向いている」「キューを使う」という特徴を持ち、一方で深さ優先探索は「行けるところまで深く探す」「メモリ消費が少ない」「スタックを使う」という特徴を持ちます。これらを表にして対比させて覚えておくことで、アルゴリズムの穴埋め問題やデータ構造を選ぶ問題に自信を持って解答できるようになります。
関連する用語
アルゴリズムの基礎となるキューというデータ構造の概念をしっかり理解することが不可欠です。また、探索アルゴリズムの双璧をなす深さ優先探索や、データ同士のつながりを表現するグラフといった用語とも関連して出題されます。