QUESTION 68
有向グラフを幅優先探索する。初めにAを訪問済みにしてFIFOキューへ入れる。以後、キューの先頭から頂点を取り出して出力し、その頂点の未訪問の行き先を表の左から順に訪問済みにしてキュー末尾へ入れる。キューへ入れる時点で訪問済みにする。出力順はどれか。 頂点 | 行き先 A | B, C B | D C | D, E D | なし E | なし
出典：本サイト オリジナル教材（2026年）
本サイトで独自に作成。IPAの試験問題からの転載ではありません。
公開日：
選択肢を選んで、答え合わせをしましょう。
回答せずに正解・解説を確認する
正解：ウ A, B, C, D, E
この表示だけでは、回答数や正答率は変わりません。
解説
Aを取り出すとキューは{B, C}、Bを取り出すと{C, D}です。Cを取り出す時点でDはすでに訪問済みなので追加せず、Eだけを入れて{D, E}になります。後はD、Eの順に出力し、全体はA, B, C, D, Eです。
ア
Bから先へ深く進んでからCへ戻る並びで、このFIFOキューによる処理順ではありません。
イ
Aの行き先はB、Cの順に追加されるため、CをBより先に取り出しません。
ウ
キューの先頭から順に処理し、同じ頂点を重ねて追加しないので、この順になります。
エ
DはBの処理でキューへ入れた時点で訪問済みとなり、Cから再度追加されません。
関連知識
幅優先探索は始点から辺の本数が少ない層から調べます。辺の重みがすべて同じ場合には、最初に見つけた経路の辺の本数が最少になります。重みが異なる最短時間の経路へ、そのまま当てはめることはできません。
間違えやすいポイント
訪問済みにする時点を取り出し時と混同しないこと。この設問は追加時なので、まだ出力されていないDでも再追加を防げます。
覚え方
FIFOで近い層から。入れた時点で訪問済み。
実務での意味
リンクの接続関係や依存関係を段階ごとに調べる際に、処理待ちキューと訪問済み集合を別々に記録します。
解説：本サイト編集部によるオリジナル文章