基本情報技術者試験「グラフ」の問題
無向グラフを次の辺リストで与える（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 辺であるため エが正しい。
✎くわしく
幅優先探索は始点から距離の昇順にノードを確定するため、終点に初めて到達したときの距離がそのまま最短ホップ数になる。深さ優先では最短性が保証されない点と対比される。
✓本番での押さえどころ
試験のコツ
BFS では『各ノードに付く距離＝最短ホップ数』であり、終点に最初に届いた距離を読む。
覚え方
『BFS で最初に着いた距離が最短』と覚える。
よくある誤り
ノード数（4 個）と辺数（3 本）を混同したり、遠回り経路を最短と誤るミスが多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 sumOdd を、引数として要素数 5 の整数型の配列 {12, 125, 1008,…次の擬似言語は、整数型の配列 arr に対して隣接交換を行う手続の一部であり、外側ループの 1 回目（1…次の擬似言語は昇順に整列された配列 arr に対する二分探索の手続である。arr = {2, 4, 6, 8, 10,…次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
```…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…スタックに対する push（積む）と…
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-b-algo-0152