深さ優先探索（DFS: Depth-First Search）は、目的のデータを見つけるため、あるいは全ての可能性を網羅するために、ツリー構造やグラフ構造を効率的に辿るアルゴリズムです。その最大の技術的特徴は、「スタック（後入れ先出しのデータ構造）」、またはプログラミング言語の「再帰呼び出し」を利用して実装される点にあります。

探索の過程では、現在いるノードからまだ訪れていない隣接ノードを一つ選び、そこへ移動します。これを限界に達するまで繰り返します。限界に達した（それ以上進めなくなった）ノードを「葉（リーフ）」と呼びますが、葉に到達すると、直前の分岐点まで戻ります。これを「バックトラック（後戻り）」と呼びます。そして、戻った分岐点から別の未訪問のルートを再び深く探索していきます。このプロセスを繰り返し、すべてのノードを訪問し終えるか、目的のデータを見つけた時点で探索が終了します。

対をなすアルゴリズムとして「幅優先探索（BFS）」がありますが、BFSが探索中のすべての分岐状態をメモリ（キュー）に保持しなければならないのに対し、DFSは現在辿っている「一つの経路（現在地までのルート）」だけをスタックに記憶しておけば済むため、使用するメモリ量が非常に少なく済むという大きな利点があります。そのため、チェスや将棋のような複雑なゲームの思考ルーチン（次の一手の先読み）や、迷路の最短ルートではなく「出口にたどり着くルートが一つでもあれば良い」といった問題、また順列や組合せをすべて生成するような場面で極めて強力な手法となります。