【解説】　幅優先探索

　幅優先探索（BFS: Breadth-First Search）は、開始点から近いノード（節点）を優先的に探索するグラフ探索アルゴリズム。水面に波紋が広がるように「層」を広げながら探索するため、全エッジの重みが等しい場合、最短経路を確実に見つけることができる。

幅優先探索の基本ポイント

特徴: 近いものから順に探索（「横型」探索）。

• 特徴: 近いものから順に探索（「横型」探索）。
• データ構造: キュー（Queue：先入れ先出し/FIFO） を使用。
• 強み: 重みなしグラフでの最短距離・最短経路計算（迷路の脱出など）。
• 弱み: 探索範囲の全ノードを記憶する必要があるため、メモリ消費量が多い。

探索のアルゴリズム

1. スタートノードをキューに追加し、「訪問済み」とする。
2. キューが空になるまで以下を繰り返す。
   • キューの先頭からノードを取り出す（調査する）。
   • そのノードに隣接する「未訪問のノード」を全てキューの末尾に追加し、「訪問済み」とする

具体的なトレース

　根（Root）を起点として、深さ1（直下のノード）→ 深さ2（孫ノード）の順に探索します。

(1) －(2) － (4)
   ＼ (3) － (5)

1. スタート: (1) をキューへ。
2. (1)を取り出し、隣接する (2), (3) をキューへ。
3. (2)を取り出し、隣接する (4) をキューへ。
4. (3)を取り出し、隣接する (5) をキューへ。
5. (4), (5) を順次処理