FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説
問題
次の幅優先探索を実行したとき，戻り値はどれか。頂点番号は1から始まる。
隣接リスト: adj[1]={2,3}, adj[2]={4,5}, adj[3]={5}, adj[4]={6}, adj[5]={6}, adj[6]={}
整数型の配列: dist ← {-1, -1, -1, -1, -1, -1}
キュー q ← 空
dist[1] ← 0
qに1をenqueueする
while (qが空でない)
v ← qからdequeueする
vに隣接する各頂点uについて
if (dist[u] = -1)
dist[u] ← dist[v] ＋ 1
qにuをenqueueする
endif
endfor
endwhile
return dist[5] × 10 ＋ dist[6]- ア 22
- イ 23
- ウ 32
- エ 33
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.x 科目B範囲
正解と解説
正解：23
正解：23
BFSでは先に見つかった距離が最短距離。1から始めると2と3は距離1，2から4と5が距離2で見つかる。3から5も見えるが，5は既に訪問済みなので更新しない。
4から6を見つけてdist[6]=3。したがって dist[5]×10+dist[6] = 2×10+3 = 23。
Hardでの確認点：BFSではキューに入った順に処理し，初めて訪問した距離が最短距離になる。既に訪問済みの頂点は再更新しないため，複数経路がある頂点では最初に入った距離を保持する。
この問題について
擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。