グラフの幅優先探索を実装するとき、次に訪問する頂点を管理するのに用いるデータ構造として、適切なものはどれか。

解説

正解は「キュー」です。幅優先探索は、始点に近い頂点から順に、同じ距離の頂点をすべて訪問してから次の距離へ進む探索です。発見した頂点をキューの末尾に追加し、先頭から取り出して訪問することで、先に見つけた（始点に近い）頂点から順に処理できます。辺に重みがないグラフでは、始点からの最短経路（辺の数）も求められます。「スタック」は、最後に見つけた頂点から先に調べる深さ優先探索で用いるデータ構造で、再帰呼出しでも実現できます。「ハッシュ表」は、訪問済みかどうかの記録には使えますが、訪問の順序は管理できません。「2分探索木」は値の大小で整理する構造で、探索順の管理には使いません。