深さ優先探索

深さ優先探索（DFS）は、グラフや木構造の探索手法の一つで、ある頂点から出発し、可能な限り深く（子ノードへ）進んでいき、行き止まりに達したら直前の分岐点に戻って未探索の枝を探索するというアルゴリズムです。スタック（再帰呼び出し）を利用して探索順序を管理し、全てのノードを訪問するまで繰り返します。経路探索やトポロジカルソート、連結成分の判定など、探索空間が大きくてもメモリ使用量が比較的少ない点が特徴で、幅優先探索と対比されながらアルゴリズム設計や問題解決に広く用いられます。