データ構造とアルゴリズム
深さ優先探索の解説（基本情報技術者シラバス用語）
深さ優先探索とは
深さ優先探索（ふかさゆうせんたんさく）とは、グラフや木構造などのデータ構造を探索するための代表的なアルゴリズムの一つです。英語の「Depth-First Search」の頭文字をとって「DFS」とも呼ばれます。この探索法の特徴は、ある経路を選んだら、突き当たり（葉ノード）に達するまでひたすら深く進み、行き止まりになったら一歩戻って（バックトラック）別のルートを探索する、という手順を繰り返すことです。メモリの消費量を抑えやすいという特徴があり、迷路の全ルートを調べたり、パズルなどの条件を満たす組み合わせをすべて列挙する問題に適しています。実装には「スタック」や「再帰」が用いられます。
具体例
一本道を進んで行き止まりにぶつかったら、最後の分岐点まで戻って別の道を進むという「迷路の探索」そのものです。木構造のフォルダの中にファイルを探しに行く場合、まず一番上のフォルダに入り、さらにその中のサブフォルダに深く潜っていき、ファイルがなければ戻って次のフォルダを調べるという手順がこれに該当します。