基本情報技術者 一問一答｜A 第64問

解説

深さ優先探索（DFS）は、グラフや木をたどる際に、一つの枝を行き止まり（最深部）まで進み、それ以上進めなくなったら直前の分岐点まで戻って（バックトラック）別の枝を探索する方式である。実装にはスタックまたは再帰呼出しを用いる。一方、幅優先探索（BFS）は出発点に近い節点から階層（幅）単位に探索する方式で、キューを用いて実装する。「階層単位で探索」はBFSの説明であり誤り。ランダム探索は系統的な探索方式ではなく、「葉から根へ」も探索の進み方の説明として不適切である。基本情報技術者試験ではDFS＝スタック・再帰、BFS＝キューという実装上の対応関係が頻出であり、木の走査順序（先行順・中間順・後行順）がDFSの一種である点もあわせて押さえたい。