深さ優先探索

深さ優先探索（ふかさゆうせんたんさく、depth-first search, DFS、バックトラック法ともいう）は、木構造 (データ構造)|木やグラフ (データ構造)|グラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラッキング|バックトラックするまで可能な限り探索を行う。「縦型探索」とも呼ばれる。