情報処理安全確保支援士試験の科目A-1などのIT国家試験において、深さ優先探索はアルゴリズムやデータ構造の問題で頻繁に出題されます。特に重要なポイントは以下の3点です。

1つ目は、「スタック（Stack）」との関連性です。「深さ優先探索を実装する際に用いられるデータ構造はどれか」という問題が出た場合、正解は必ず「スタック」になります。スタックは「最後に入れたデータを最初に取り出す（LIFO: Last In First Out）」という性質を持っており、これが直前の分岐点に戻るバックトラックの動きと完全に一致するからです。なお、キュー（Queue）は幅優先探索で用いられるため、引っかけの選択肢としてよく登場するので注意が必要です。

2つ目は、「木構造の巡回順序」に関する問題です。二分木（各ノードが最大2つの子を持つ木構造）を深さ優先探索で巡回する順序には、「先行順（行きがけ順）」「中間順（通りがけ順）」「後行順（帰りがけ順）」の3種類があります。試験では「図で示された木を中間順で巡回したときに、ノードを訪問する順番として正しいものはどれか」といった問題がよく出ます。左の子、親、右の子という順番で辿るのが中間順など、それぞれの定義をしっかりと図に描いてトレースできるようにしておくことが不可欠です。

3つ目は、「再帰アルゴリズム」との組み合わせです。疑似言語を用いたプログラミング問題において、深さ優先探索は関数が自分自身を呼び出す「再帰処理」を使って記述されることがほとんどです。プログラムのトレース問題が出た際には、関数がどの深さまで呼び出され、どのタイミングで値が返ってくるか（再帰の終了条件は何か）を、余白にスタックの状態をメモしながら落ち着いて追いかける計算力が求められます。

幅優先探索、スタック、再帰呼び出し