FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：次の手続 bfsOrder() を実行したときの戻り値はどれ…
問題
次の手続 bfsOrder() を実行したときの戻り値はどれか。
○整数型: bfsOrder()
グラフの辺: (1,2), (1,3), (2,5), (3,4), (3,6), (4,5), (5,6)
dist[1] ← 0, dist[2]〜dist[6] ← -1
整数型: order ← 0
キュー q ← 空
enqueue(q, 1)
while (qが空でない)
v ← dequeue(q)
order ← order ＋ 1
if (v = 5)
return order × 10 ＋ dist[v]
endif
vに隣接する各頂点 u について番号の小さい順に調べる
if (dist[u] = -1)
dist[u] ← dist[v] ＋ 1
enqueue(q, u)
endif
endfor
endwhile
return 0- ア 32
- イ 42（正解）
- ウ 52
- エ 23
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：42
BFSは1を取り出して order=1、2と3を入れます。次に2を取り出して order=2、5を入れます。次に3を取り出して order=3、4と6を入れます。次に5を取り出すので order=4、dist[5]=2となります。戻り値は4×10+2=42です。
32は3番目に5を取り出すと誤った場合、52は距離と取り出し順をずらした場合に出やすい値です。23は dist[5] だけを先に見て order を無視しています。
BFSでは発見順と取り出し順が一致しない場合があります。enqueueした時点ではなく、dequeueしてorderを増やす時点を追いましょう。
dist が表すもの：BFSの dist は始点1からの最短経路の辺数（距離）を表し、dist[5]=2 は 1→2→5 と2本の辺でたどり着けることを示します。1からの距離は0、2と3が1、4・5・6が2という層になり、同じ層の頂点は番号の小さい順にキューへ入った順で取り出されます。最短距離と取り出し順は別物だと意識すると混同を防げます。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。