アルゴリズムとプログラミングアルゴリズム実践

グラフ探索における深さ優先探索(DFS)と幅優先探索(BFS)の特徴比較として正しいものはどれか。

ア.BFSはスタックを使い、DFSはキューを使って実装する

イ.DFSは最短経路を求めるのに最適であり、BFSは迷路の出口発見に適している

ウ.BFSは出発点からの距離が近いノードを先に探索するため、重みなしグラフの最短経路を求めるのに適している正解

エ.DFSとBFSはどちらも同一の計算量O(V+E)であるが、使用するメモリ量も常に同じである

解説

DFSは「一本道を突き進む冒険者」、BFSは「同心円状に広がる水の波紋」みたいなもの。BFSは出発点から波紋が広がるように距離1の点、距離2の点と順番に探索する。だから最初に見つかったときの経路が必ず最短！DFSは深く潜るから遠回りを先に見つけることもある。

なぜウが正解か

BFSの最短経路適性の理由：①キューを使ってFIFO（先入れ先出し）で探索②距離(hop数)が小さいノードから順番に処理③重みなしグラフでは、あるノードを初めて発見したとき、それが最短距離での到達を保証。したがってBFSは迷路最短ルート・SNSの最短友人関係数などに活用される。

なぜアは間違いか

逆。DFSはスタック（または再帰）を使い、BFSはキューを使う。スタックとキューの使い分けがDFS/BFSの実装上の核心的違い。

なぜイは間違いか

最短経路を求めるのに最適なのはBFS（重みなしグラフ）。DFSは最短経路の保証がなく、迷路の出口発見より連結性確認や閉路検出に向いている。説明が逆になっている。

なぜエは間違いか

計算量O(V+E)は同じだが、メモリ使用量は異なる。DFSは再帰の深さ分のスタック（最悪O(V)）、BFSは探索待ちノードのキュー（最悪O(V)）で、グラフの形状によって実際の使用量は大きく異なる。

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

← 前の問題

線形探索と二分探索の使い分けとして最も適切なものはどれか。

次の問題 →

A*アルゴリズムについての説明として最も正しいものはどれか。