【びーえふえす】

BFS（幅優先探索）とは？

最終更新: 2026年10月4日

💡 一歩先を調べてから、二歩先へ広がる

始点からたどれるノードを、通る辺の数が少ない順に探索するアルゴリズム。キューで探索順を管理し、重みのないグラフで最少の辺数となる経路を求められる。

📌 このページのポイント

線はノード間の接続を示す。距離は始点Aから通る辺の数で、同じ距離のノードの順序は隣接ノードを調べる順に依存する。

ひよこ

BFSってどういう探索なの？

ペンギン先生

始点から1本の辺で行ける場所を調べ、次に2本で行ける場所へ……と広がる探索法だよ。ここで「近い」は画面上の距離ではなく、通る辺の数。始点からつながっていない場所には到達しないんだ。

ひよこ

水面の波紋みたいな感じかな？

ペンギン先生

浅い段階から広がる点は似ているね。重みのないグラフなら、初めて到達した経路の辺数は最少になる。道路ごとの移動時間のように辺の費用が違う場合、その合計の最短を普通のBFSで保証することはできないよ。

ひよこ

どうやって次に調べる場所を覚えるの？

ペンギン先生

先に入れたものから取り出すキューを使うんだ。新しく見つけた場所を訪問済みにしてからキューへ入れると、輪になった道や複数の経路があっても同じ場所を何度も登録せずに済むよ。

ひよこ

DFSとはどう違うのかな？

ペンギン先生

DFSは一つの道を深く進んでから戻り、BFSは同じ深さの場所を先に調べるよ。重みなしで辺数の最少経路が欲しいならBFSが使える。DFSで一度探索するだけで、すべての経路が列挙されるわけではないんだ。

ひよこ

どんな問題に使えるの？

ペンギン先生

1回の操作を1本の辺と考えたパズルの最少手数や、人間関係の何段先かを調べる例があるよ。隣接リストで表す一般的な実装なら時間はO(V+E)、グラフ自体を除く追加メモリはO(V)。Vはノード数、Eは辺数だね。

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

「BFS」って出てきたら「始点からたどれる場所を、辺の数が少ない順に調べる探索法」と思えばだいたいOK！

📖 おまけ：英語の意味

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

💬 Breadth（幅）を先に広げてから深くに進む探索だから、この名前が付いたんだよ

参考資料