アルゴリズムとプログラミング
基本情報技術者試験｜無向グラフを次の辺リストで与える（u — v は u と v を結ぶ辺）。 1—2, 1—3, 2—4,…
無向グラフを次の辺リストで与える（u — v は u と v を結ぶ辺）。
1—2, 1—3, 2—4, 3—4, 3—5, 4—6, 5—6
次の手続 shortestHops は、幅優先探索を用いて始点 s から終点 t までの最短ホップ数（経由する辺の本数）を返す。shortestHops(1, 6) を実行したとき、戻り値はどれか。
○整数型: shortestHops(整数型: s, 整数型: t)
queue ← 空のキュー
dist[s] ← 0
visited[s] ← true
enqueue(s)
while (queue が空でない)
整数型: u ← dequeue()
if (u が t と等しい)
return dist[u]
endif
整数型: v
for (v を 1 から 6 まで 1 ずつ増やす)
if (辺 u—v が存在 かつ visited[v] が false)
visited[v] ← true
dist[v] ← dist[u] + 1
enqueue(v)
endif
endfor
endwhile
return -1ア5 ホップ（遠回り経路）
イ2 回
ウ4 ホップ
エ3 ホップ
正解
エ．3 ホップ
幅優先探索で距離を付けると dist は 1:0、2:1、3:1、4:2、5:2、6:3 となる。6 に初めて到達する距離は 3 であり、最短経路（例 1—2—4—6）が 3 辺であるため エが正しい。
?選択肢ごとの解説
ア ×経由するノード数や遠回り経路（1—3—5—6 を辺数で誤算）から 5 ホップとした、最短性を確認しなかった過大評価である。
イ ×1—?—6 の 2 辺で行けると誤認した、1 と 6 を直接または 1 ノード経由でつなぐ辺が存在しないことを見落とした誤りである。
ウ ×遠回りの 1—3—5—6 を 4 辺と数えるなどして 4 ホップとした、より短い 3 辺の経路を見落とした誤りである。
エ ○幅優先探索で距離を付けると dist は 1:0、2:1、3:1、4:2、5:2、6:3 となる。6 に初めて到達する距離は 3 であり、最短経路（例 1—2—4—6）が 3 辺であるため エが正しい。
アルゴリズムとプログラミングの他の問題
無向グラフを次の辺リストで与える（u — v は u と v を結ぶ辺）。
1—2, 2—3, 4—5
次の手続…有向グラフを次の辺リストで与える（u → v は u から v への辺）。
1→3, 2→3, 4→3, 2→5, 4→5…6 個のノード（番号 1〜6）からなる有向グラフを次の辺リストで与える（u → v は u から v への辺）。
1→2,…4 個のノード 1〜4 から成る有向グラフを隣接行列 M で表す。M[i][j]=1 ならノード i から j…頂点数nのグラフを隣接行列で表現したとき、必要な記憶領域の大きさのオーダはどれか。5 個のノード 1〜5 から成る無向グラフを、隣接行列 M で表す。M[i][j] が 1 ならノード i と j…有向グラフを次の辺リストで与える（u → v は u から v への辺を表す）。
1→2, 1→4, 2→3, 2→5,…有向グラフを次の辺リストで与える（u → v は u から v への辺を表す）。
1→2, 1→4, 2→3, 4→5,…
この問題の「深掘り・誤答の完全解説・覚え方」は、登録すると読めます。
基本情報技術者試験は全4,036問。公開しているのはその一部で、登録すると残りも一問ごとにAI解説つきで解けます。SRS暗記カード・全真模試・弱点診断まで。
登録は1分・クレジットカード不要。無料のまま練習・暗記カード・模試まで使えます。
作成・校閲：ukamiru編集部 · 基本情報技術者試験 過去問 · fe-b-algo-0152