FE SUBJECT B
基本情報技術者 科目Bの問題解説
問題
次の幅優先探索を実行したとき，戻り値はどれか。頂点番号は1から始まる。
整数型の配列の配列: adj ← {{2,3}, {4,5}, {5}, {6}, {6}, {}}
整数型の配列: q, order
enqueue(q, 1)
visited[1] ← true
while (qが空でない)
v ← dequeue(q)
append(order, v)
for (adj[v]の各要素 u を先頭から順に取り出す)
if (visited[u] = false)
visited[u] ← true
enqueue(q, u)
endif
endfor
endwhile
return order[5]- ア 3
- イ 4
- ウ 5
- エ 6
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：5
正解：5
幅優先探索では，キューから取り出した順にorderへ追加する。1を取り出した後に2,3を入れ，2を取り出した後に4,5を入れる。3から5へ行く辺もあるが，5はすでにvisited=trueなので重複して入れない。
| 取り出し | 処理後のキュー | order |
|---|---|---|
| 1 | {2,3} | {1} |
| 2 | {3,4,5} | {1,2} |
| 3 | {4,5} | {1,2,3} |
| 4 | {5,6} | {1,2,3,4} |
| 5 | {6} | {1,2,3,4,5} |
order[5]は5。隣接リストの順序と，visitedをenqueue時にtrueへする点を追う。
選択肢の見分け方：3や4は途中で取り出された頂点，6は5の次に取り出される頂点である。BFSでは発見した時点でvisitedにするため，同じ頂点をキューへ二重登録しない。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。