BFSとDFSの違い
正解
辺の重みがすべて等しい（または重みなし）グラフでは、BFSは最短経路を保証する。DFSは一つの枝を深く優先する。
正解になる理由
BFSは始点からの辺数（ホップ数）の順に展開します。各辺のコストが等しいときに、初めて見つけたゴールが最短です。重みが異なるグラフではダイクストラやA*が必要です。DFSは深く進むため、解の発見は早いことがありますが最短は保証しません。
各誤答がなぜ誤りか
- 選択肢1: DFSは無限分岐や閉路の扱いで完全性を失い得ます。重み付き最短も保証しません。
- 選択肢2: どちらも再帰・反復で実装できます。BFSはキュー、DFSはスタックが典型です。
- 選択肢4: BFSはフロンティアが大きくなりメモリを食いやすく、速度も問題依存です。
G検定でのひっかけポイント
「BFS＝最短」は重みなし／均一コストの条件付きです。