幅優先探索と深さ優先探索の違いを徹底解説！中学生にもわかる実例つきの図解

---

幅優先探索と深さ優先探索とは何か

まず幅優先探索と深さ優先探索は、迷路やネットワークの中を探索する際の基本的な考え方です。どちらもゴールに近づく道筋を順序立てて調べますが、たどり方が大きく異なります。この記事では中学生にも分かるように、実例を交えながら丁寧に解説します。

まず幅優先探索、BFS は名前のとおり“幅”を広く扱います。
出発点から隣接するノードを次々に取り出していき、まだ調べていないノードをキューに入れておきます。待ち行列のように並んだノードを順番に展開していくので、現在到達した場所の距離が徐々にわかるようになります。
未加重のグラフで最短経路を見つけやすいという特徴があり、途中経路の候補を段階的に絞り込めます。これは迷路のスタート地点からゴールまで“最短の道”を見つけたいときにとても有効です。

直感で分かる違い

幅優先探索は、最初の一歩から広がるたびに新しい道を広く検討していくイメージです。
一方で深さ優先探索、略して DFS は“深さを優先”します。
DFS は現在の道をどんどん深く進んでいき、行き止まりにぶつかったら戻って他の道を試します。
このとき再帰やスタックを使って履歴を覚えることで、すでに進んだ道をもう一度たどらなくて済むようにします。
DFSはメモリを節約できる場合がある反面、深く潜るほど探索の時間が長くなることがあります。

直感的には、BFSは“近いところから順番に調べる”、DFSは“深く潜ってから戻る”イメージです。どちらを選ぶかで、見つかる解の性質が変わります。

現実の例で考える

迷路を例にすると、BFSはスタートから同じ距離の分岐を同時に調べるため、ゴールまでの最短距離が保証されやすいです。
迷路が広く複雑でも、ゴールまでの道が短い場合は早く見つかります。
DFSは端から探していくので、偶然長い道を選ぶと時間がかかることがありますが、構造が木のように細長い場合には少ないメモリで完結することもあります。
実務では、最短距離が大切な場面では BFS を、深い探索が重要な場面や再帰的な木構造の処理には DFS を選ぶのが基本です。

使い分けのコツと実践ポイント

実際のプログラムでは、データ構造と問題の性質をよく観察して選ぶことが大事です。
未加重のグラフで“最短経路”を狙うなら BFS、特定のパスをできるだけ深く辿ってみたい場合は DFS が向いています。
メモリの制約がある環境では、DFS の再帰を避けてスタックを自作して使う方法も有効です。
また、探索の途中で訪問済みノードを記録することは、同じ場所を何度も訪問しないようにする基本です。
時間と空間のトレードオフを意識して使い分けることが、効率的なアルゴリズム設計の第一歩です。

ゲームや迷路での具体例

ゲームの迷路を思い浮かべると分かりやすいです。
BFS は“近い場所を速く探す”のに向いており、▶ゴールが手の届く距離にある場合すぐ発見されます。
DFS は“長い道をじっくり試す”タイプの動作に近く、複雑なネットワークでの探索にも適しています。
競技プログラミングでは、問題文の条件に合わせて BFS か DFS を選ぶ練習を繰り返すと力がつきます。
表のような比較表を頭に入れておくと、迷路やグラフの問題に直面したときに迷わず選択できるようになります。

able> 特性BFSDFS 探索順階層ごとに広がる深く潜る メモリ使用現在の階層のノード数分再帰スタックや visited の合計量 最短経路の発見あり場合によってはなし 実装の難易度比較的低い再帰で直感的だが深くなると難しい ble>

ピックアップ解説

ねえ、さっきの迷路の話を雑談風にしてみよう。僕は幅優先探索のことを考えると、最初の一歩でいろんな道が同時に開かれていく感じが好きなんだ。幅優先探索は入口付近の道を近い順に切り分けていくイメージで、最短距離を保証してくれることが多い。だけど、広いマップだと同時に覚える場所が増えてしまい、メモリの管理が難しくなることもある。だから僕は、場面に応じて BFS と DFS を使い分ける練習をして、どういう場面でどちらを選ぶべきかを体感で覚えたいと思っている。

---