深さ優先探索（ふかさゆうせんたんさく、英: depth-first search, DFS、バックトラック法ともいう）は、木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な限り探索を行う。「縦型探索」とも呼ばれる。
深さ優先探索のイメージ
概要
形式的には、深さ優先探索は、探索対象となる木の最初のノードから、目的のノードが見つかるか子のないノードに行き着くまで、深く伸びていく探索である。その後はバックトラックして、最も近くの探索の終わっていないノードまで戻る。非再帰的な実装では、新しく見つかったノードはスタックに貯める。
深さ優先探索の空間計算量は幅優先探索の空間計算量より最悪のケースでは同じだが一般的なケースではずっと小さい。また、探索の種類によっては、分岐を選択するためのヒューリスティックな方法にも向いている。両者の時間計算量は、最悪のケースではノード数とたどる辺の数の合計に比例する。
擬似コード
再帰あり
function 深さ優先探索(v) v に訪問済みの印を付ける v を処理する for each v に接続している頂点 i do if i が未訪問 then 深さ優先探索(i)
再帰なし
function 深さ優先探索(v) S ← 空のスタック v に訪問済みの印を付ける v を S に積む while S が空ではない do v ← S から取り出す v を処理する for each v に接続している頂点 i do if i が未訪問 then i に訪問済みの印を付ける i を S に積む
Pythonでの実装(再帰なし)
以下は、2頂点間の経路を探す例。なお、これを幅優先探索でやると、辺の重みなしの最短経路問題になる。
def depthFirstSearch( start, goal ): stack = Stack() start.setVisited() stack.push( start ) while not stack.empty(): node = stack.top() if node == goal: return stack # stack には2頂点間の経路が入っている else: child = node.findUnvisitedChild() if child == none: stack.pop() else: child.setVisited() stack.push( child ) 反復深化深さ優先探索
詳細は「反復深化深さ優先探索」を参照
関連項目
外部リンク
- 『深さ優先探索と幅優先探索』 - 高校数学の美しい物語
- Depth-First Search Animation (for a directed graph)
- Another Depth-First Search Animation (for a directed graph - recursive)