FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：次の深さ優先探索をスタックで実行したとき、戻り値はどれか。 …
問題
次の深さ優先探索をスタックで実行したとき、戻り値はどれか。
整数型の配列の配列: adj ← {{2,3}, {4}, {4,5}, {6}, {6}, {}}
整数型の配列: stack, order
push(stack, 1)
while (stackが空でない)
v ← pop(stack)
if (visited[v] = false)
visited[v] ← true
append(order, v)
for (adj[v]の各要素 u を先頭から順に取り出す)
if (visited[u] = false)
push(stack, u)
endif
endfor
endif
endwhile
return order[4]- ア 3
- イ 4
- ウ 5
- エ 6（正解）
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：6
スタックは後入れ先出しです。頂点1で2，3の順にpushすると、次にpopされるのは後から入った3です。さらに3から4，5をpushするため、5が先に処理されます。
| pop | push後のstack | order |
|---|---|---|
| 1 | {2,3} | {1} |
| 3 | {2,4,5} | {1,3} |
| 5 | {2,4,6} | {1,3,5} |
| 6 | {2,4} | {1,3,5,6} |
4番目にorderへ入る頂点は6です。幅優先探索のキュー順と混同しないようにしましょう。
選択肢の見分け方：3や5は途中の訪問頂点、4はスタック下に残っている頂点です。隣接頂点をpushした順と、popされる順が逆になることを必ず確認しましょう。
再帰版との違い：同じ深さ優先探索でも、隣接頂点を素直にpushするスタック版では後から積んだ頂点が先にpopされるため、隣接リスト{2,3}のうち3が先に展開されます。再帰で書くと先頭の2から探索が進み、訪問順は1→2→4→6となって結果が変わります。スタックで前方優先の順序を得たい場合は、隣接要素を逆順にpushする必要がある点に注意しましょう。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。