基本情報技術者試験「グラフ」の問題
有向グラフを次の辺リストで与える（u → v は u から v への辺を表す）。
1→2, 1→4, 2→3, 2→5, 3→5
次の深さ優先探索 dfs をノード 1 から開始する。隣接ノードは番号の小さい順に選び、未訪問のノードのみ再帰的に訪問する。訪問した順にノード番号を出力するとき、その出力列はどれか。
○手続: dfs(整数型: u)
visited[u] ← true
出力(u)
整数型: v
for (v を 1 から 5 まで 1 ずつ増やす)
if (辺 u→v が存在 かつ visited[v] が false)
dfs(v)
endif
endforア1→2→4→3→5（幅優先的順序）
イ1→2→3→5→4
ウ1→4→3→5
エ1→2→3→4→5
正解
イ．1→2→3→5→4
深さ優先探索は隣接先へ可能な限り深く進む。1 の最小隣接 2 へ入り、2→3→5 と潜って行き止まり、戻って 1 の次の隣接 4 を訪問する。よって 1→2→3→5→4 となり イが正しい。
?選択肢ごとの解説
ア ×1 の全隣接 2,4 を先に並べてから深くたどっており、これは幅優先的な順序であって深さ優先ではない誤りである。
イ ○深さ優先探索は隣接先へ可能な限り深く進む。1 の最小隣接 2 へ入り、2→3→5 と潜って行き止まり、戻って 1 の次の隣接 4 を訪問する。よって 1→2→3→5→4 となり イが正しい。
ウ ×1 の隣接を大きい番号 4 から先に選び、さらに 2 を飛ばしており、『小さい順かつ全ノード訪問』の規則に二重に反する誤りである。
エ ×5 を最後に回し 4 を 3 の後に挿入しており、再帰の戻りタイミングを取り違えた誤りである。
✎くわしく
深さ優先探索は『行けるところまで深く、行き止まりで一段戻る』。再帰呼び出しが完了して初めて呼び出し元の次の隣接へ進む点が、幅優先との決定的な違いである。
✓本番での押さえどころ
試験のコツ
再帰の呼び出し・戻りをスタックの出入りとして紙に書き、最深部に達したら 1 つ戻る動きを追う。
覚え方
『DFS は深掘り、行き止まりで Uターン』と覚える。
よくある誤り
1 の隣接を一度にすべて訪問してしまい、幅優先と混同するミスが最も多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 sumOdd を、引数として要素数 5 の整数型の配列 {12, 125, 1008,…次の擬似言語は、整数型の配列 arr に対して隣接交換を行う手続の一部であり、外側ループの 1 回目（1…次の擬似言語は昇順に整列された配列 arr に対する二分探索の手続である。arr = {2, 4, 6, 8, 10,…次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
```…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…スタックに対する push（積む）と…
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-b-algo-0146