アルゴリズムとプログラミングアルゴリズムとデータ構造

グラフの探索アルゴリズムである幅優先探索（BFS）と深さ優先探索（DFS）の説明として、最も適切なものはどれか。

ア.幅優先探索はキューを用いて開始ノードに近いノードから順に探索し、深さ優先探索はスタック（または再帰）を用いてできる限り深くノードをたどってから折り返す。正解

イ.幅優先探索はスタックを用いて開始ノードから近い順に探索し、深さ優先探索はキューを用いてできる限り深くノードをたどってから折り返す。

ウ.幅優先探索と深さ優先探索は、どちらも同じ順序でノードを探索するが、使用するメモリ量だけが異なる。

エ.幅優先探索は有向グラフにのみ適用でき、深さ優先探索は無向グラフにのみ適用できる。

解説

BFSは池に石を落としたときの波紋のように「スタートから近い順」に広がる探索で、DFSは迷路を「行き止まりまで突き進んでから引き返す」探索です。この動き方の違いが、使うデータ構造（キューとスタック）の違いに直結しています。

なぜアが正解か

BFSはキュー（FIFO：先入れ先出し）を使います。隣接ノードをキューの末尾に追加し、先頭から取り出して処理するため、スタートに近いノードを先に処理でき、距離ゼロ→距離1→距離2と層単位で探索が広がります。DFSはスタック（LIFO：後入れ先出し）または再帰を使います。最後に追加したノードを先に処理するため、常に「今いる場所から一番先に進んだ方向」を優先し、行き止まりに当たって初めて引き返す動きになります。

なぜイは間違いか

BFSとDFSのデータ構造が入れ替わっています。BFSにスタックを使ってしまうと、最後に追加したノード（＝より深い方向のノード）を先に処理することになり、「近い順」ではなく「深い順」の探索になってしまいます。これはまさにDFSの動きです。BFS・DFSは名前よりも「キューかスタックか」で動作を理解すると混同しにくくなります。

なぜウは間違いか

BFSとDFSは探索順序が根本的に異なります。BFSは「スタートから距離1の全ノード→距離2の全ノード→…」と層ごとに網を張るように探索しますが、DFSは「1本の枝を最深部まで追い切ってから次の枝へ」と探索します。同じ順序にはなりません。なお、メモリ使用量も異なる（BFSはノード数が多いとキューが膨らみやすい）ため、この選択肢は前半・後半ともに誤りです。

なぜエは間違いか

BFSもDFSも、有向グラフ・無向グラフのどちらにも適用できます。グラフの「向き」は辺をどの方向にたどれるかを決めるものであって、探索アルゴリズムの適用可否とは別の話です。有向グラフでは辺の向きに従ってノードをたどるだけで、アルゴリズム自体は変わりません。

出典: AI生成問題（学習用）

← 前の問題

n個の要素を整列するとき、要素の初期配置に関わらず最悪の場合でも時間計算量がO(n log n)となることが保証されている整列アルゴリズムはどれか。

次の問題 →

n 個のデータをソートするとき、最悪計算量が O(n²) となるソートアルゴリズムはどれか。

アルゴリズムとプログラミングの問題を解くこの分野の問題一覧を見る