問題
深さ優先探索（DFS）と幅優先探索（BFS）の特性に関する記述のうち、適切なものはどれか。
選択肢
- 1DFS はキューを、BFS はスタックを用いて実装される。
- 2BFS は無向グラフで始点から各頂点までの最短経路（辺の本数）を求めるのに適している。
- 3DFS は必ず最短経路を発見するが計算時間がかかる。
- 4BFS は再帰呼出しで自然に実装でき、メモリ効率が高い。
正解
2. BFS は無向グラフで始点から各頂点までの最短経路（辺の本数）を求めるのに適している。
詳しい解説を見る解説を閉じる
解説
BFS はキューを用い、辺の重みが等しい（または無重み）グラフで始点からの最短経路（辺の本数）を求めるのに適する。1は逆（DFSがスタック、BFSがキュー）。3はDFSが最短経路を保証するとは限らない。4は再帰で自然に実装できるのはDFS。
一問一答
全400問を繰り返し学習