幅優先探索（BFS）とは何ですか？

グラフやツリーを探索するアルゴリズムの一つで、出発点から近い順にすべてのノードを調べていく方法。最短経路の発見に向いている。

幅優先探索（BFS）のポイントは？

出発ノードに近い順（同じ深さのノードを先に）探索する。キュー（FIFO）を使って実装する。重みなしグラフでの最短経路を保証できる。深さ優先探索（DFS）と対になる基本的な探索手法

【はばゆうせんたんさく】

💡 近くから順に、じわじわ広がる探索の波

📌 このページのポイント

幅優先探索のイメージ

ひよこ

幅優先探索ってどういう探し方なの？

ペンギン先生

池に石を投げたときの波紋をイメージしてみて。出発点から近い順に同心円状に広がりながら探索していく方法だよ

ひよこ

具体的にはどう動くの？

ペンギン先生

まず出発ノードをキューに入れる。キューから一つ取り出して、そのノードの隣接ノードを全部キューに追加する。これを繰り返すと、深さ1のノードが全部終わってから深さ2に進む形になるんだ

ひよこ

どんな場面で使うの？

ペンギン先生

重みなしグラフでの最短経路探索が代表的だね。カーナビの経路探索や、SNSで『友達の友達』をたどる機能、迷路の最短解法なんかにも使われるよ

ひよこ

深さ優先探索と使い分けるポイントは？

ペンギン先生

最短経路がほしいならBFS、全パターンを調べ尽くしたいならDFSが向いているよ。ただしBFSは探索済みノードをすべてメモリに保持するから、グラフが巨大だとメモリを大量に消費するのが弱点だね

ひよこ

計算量はどのくらいなの？

ペンギン先生

ノード数Vとエッジ数Eとして O(V+E) だよ。各ノードを1回ずつ、各エッジを1回ずつ調べるから効率的なんだ。双方向BFSという改良版もあって、スタートとゴールの両側から同時に探索すると探索範囲を大幅に減らせるよ

まとめ：ざっくりこれだけ覚えればOK！

「幅優先探索」って出てきたら「近い順に全方向へ広がりながら探す方法」と思えればだいたいOK！

📖 おまけ：英語の意味

「Breadth-First Search」＝幅優先探索

💬 「breadth（幅）」を「first（最初に）」探索するという名前で、横に広がりながら調べていくイメージだよ