FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：木構造における深さ優先探索（DFS）の特徴はどれか。
問題
木構造における深さ優先探索（DFS）の特徴はどれか。
- ア 葉ノードから根に向かって逆順に探索する方法
- イ 根から同じ深さのノードを全て探索してから、次の深さに移る探索方法
- ウ ランダムにノードを選択して探索する方法
- エ 根から葉まで一つの枝を深く探索してから、次の枝に移る探索方法（正解）
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目A範囲
正解と解説
正解：根から葉まで一つの枝を深く探索してから、次の枝に移る探索方法
正解はエ：深さ優先探索（DFS）は、根から出発して一つの枝をできるだけ深く進み、行き止まりになったら戻って別の枝を探索する方法です。スタックを使うか、または再帰呼び出しで実装されることが多いです。
イメージ：例えば、迷路で「進めるところまで進み、進めなくなったら直前の分岐点に戻る」ような探索がDFSのイメージに近いです。木構造だけでなく、グラフ探索でも利用されます。
ほかの選択肢：イは幅優先探索（BFS）で、同じ深さのノードを先に調べます。BFSはキュー、DFSはスタックまたは再帰、と対応づけて覚えるとよいでしょう。
関連用語の整理：木構造のDFSは、ノードを訪問する順序によって前順（行きがけ＝根→左→右）、中順（通りがけ＝左→根→右）、後順（帰りがけ＝左→右→根）に分かれます。特に二分探索木を中順で巡回すると、値が昇順に並んで取り出せる点が頻出です。
他の選択肢はなぜ違う？
- ア葉から根へ逆順にたどるという探索ではない。
- イ同じ深さを全部見てから次へ進むのは幅優先探索（BFS）。
- ウランダム選択は探索アルゴリズムの説明になっていない。
この問題について
IPAが公開するシラバス・試験範囲・公開問題の出題形式を参考にした独自作成問題。公式問題・過去問題の転載ではありません。
公式試験問題、過去問題、公式サンプル問題、市販教材の問題文を転載したものではありません。