深さ優先探索（DFS）と幅優先探索（BFS）の比較
探索アルゴリズムの中でも基本となる「深さ優先探索（DFS）」と「幅優先探索（BFS）」。G検定ではこの2つの「探索の動き方の違い」と「メリット・デメリット」の比較が頻出です。それぞれの特徴を整理し、違いを明確に覚えましょう。
深さ優先探索（DFS）
解説
深さ優先探索（Depth-First Search）は、「とにかく突き進む」探索手法です。
探索木の根（スタート）から始まり、一つの分岐を選んで行けるところまで奥深く進みます。行き止まり（葉）に達して初めて、一つ手前の分岐点に戻り（バックトラック）、まだ選んでいない別の道を進みます。
データ構造には、最後に入れたものを最初に取り出す「スタック（Stack / LIFO）」が用いられることが特徴です。
- 動きのイメージ：迷路で「右手を行き止まりまで壁伝いに進む」ような動き。
- メリット：現在の経路の情報だけを記憶すればよいため、メモリ消費量が少ない。
- デメリット：最初に見つかったゴールが、必ずしもスタートから一番近い（最短）とは限らない。解が深い階層にある場合、見つけるのに時間がかかる。
幅優先探索（BFS）
解説
幅優先探索（Breadth-First Search）は、「しらみつぶしに広げる」探索手法です。
スタート地点から近いノード（浅い階層）をすべて探索し終えてから、次の深さの階層へと進みます。出発点から等距離にある場所を波紋が広がるように調べていくイメージです。
データ構造には、最初に入れたものを最初に取り出す「キュー（Queue / FIFO）」が用いられます。
- 動きのイメージ：RPGゲームでマップの周囲をすべて埋めてから、次のエリアに進む動き。
- メリット：スタートから近い順に探すため、最短経路（ステップ数）を発見しやすい。
- デメリット：探索するノードすべてを記憶しておく必要があるため、探索範囲が広がるとメモリ消費が膨大になる。
【まとめ】DFSとBFSの違い一覧
試験直前の確認用に、2つの違いをまとめました。
| 比較項目 | 深さ優先探索 (DFS) | 幅優先探索 (BFS) |
|---|---|---|
| 探索の優先順 | 縦方向（深さ）優先 | 横方向（幅）優先 |
| データ構造 | スタック (LIFO) | キュー (FIFO) |
| メモリ消費 | 少ない (有利) | 多い (不利) |
| 最短経路 | 保証されない | 見つけやすい |
| キーワード | バックトラック、再帰処理 | 最短手数は？、全探索 |
