FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：次の深さ優先探索を実行したとき、戻り値はどれか。 整数型の二…
問題
次の深さ優先探索を実行したとき、戻り値はどれか。
整数型の二次元配列: g ← {{0,1,1,0,0}, {0,0,0,1,0}, {0,0,0,1,1}, {0,0,0,0,0}, {0,1,0,0,0}}
整数型: sum ← 0
○手続: dfs(整数型: v)
visited[v] ← true
sum ← sum ＋ v
for (u を 1 から 5 まで 1ずつ増やす)
if (g[v][u] = 1 and visited[u] = false)
dfs(u)
endif
endfor
dfs(1) を呼び出す。
return sum- ア 10
- イ 12
- ウ 15（正解）
- エ 18
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：15
dfsでは頂点番号の小さいuから順に調べます。1から2へ進み、2から4へ進みます。4からは進めないので戻り、次に1から3へ進みます。3から4は訪問済みなので飛ばし、5へ進みます。
| 訪問順 | sum |
|---|---|
| 1 | 1 |
| 1,2 | 3 |
| 1,2,4 | 7 |
| 1,2,4,3 | 10 |
| 1,2,4,3,5 | 15 |
すべての到達頂点1〜5を一度ずつ足すので15です。5から2への辺はありますが、2は訪問済みのため再帰しません。
選択肢の見分け方：10は5を訪問し忘れた値、12や18は訪問済み頂点を再度足した場合に出やすい値です。visitedにより、各頂点はsumへ一度だけ加算されます。
このコードの計算量：隣接行列でDFSを行うと、各頂点vから常に1〜5の全列を調べるため、頂点数をnとして処理量はO(n²)になります。隣接リストならO(n+辺数)に減らせます。本問では辺5→2のように訪問済み頂点へ戻る辺があっても、visited[u]の判定で再帰を打ち切るため無限ループにならず、各頂点はsumへ一度だけ加算されます。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。