辺に重みのないグラフで、出発点から各頂点までの最短の辺の数を求めたい。適した探索の方法と、そのとき使うデータ構造の組はどれか。

正解：A. 幅優先探索と、キュー

幅優先探索は、出発点から辺1本で行ける頂点、2本で行ける頂点…と、近い順に訪れます。見つけた頂点をキューの末尾に入れ、先頭から取り出して調べることで、この「近い順」が保たれるので、最初に到達したときの辺の数がそのまま最短の数になります。深さ優先探索(再帰やスタックを使う)は1本の道を行けるところまで進むので、遠回りの経路で先に到達することがあり、最短は保証されません。キューの代わりにスタックを使うと、深さ優先探索に近いたどり方になってしまいます。

• A. 正しい。キューを使うと出発点から近い順に訪れるので、最短の辺の数が求まります。
• B. 深さ優先探索は遠回りの経路で先に到達することがあり、最短は保証されません。
• C. スタックを使うと最後に見つけた頂点から調べるので、近い順に訪れなくなります。