深さ優先探索

深さ優先探索とは、一つの枝をできるだけ深く、行き止まりまで進んでから、戻って別の枝を試す探索方法です。とにかく先へ先へと進む点が幅優先探索と対照的です。

迷路でいえば「とりあえず一本道を最後まで進み、ダメなら一つ戻って別の道を試す」というやり方にあたります。メモリの使用量が少なくて済む長所がありますが、最初に見つかった道が最短経路とは限りません。

幅優先探索と深さ優先探索は探索の基本となる2大手法で、問題の性質に応じて使い分けます。