深さ優先探索

深さ優先探索
	Order in which the nodes get expanded; 探索順
一般的な情報
分類:	探索アルゴリズム
データ構造:	グラフ
時間計算量:
空間計算量:
最適:	いいえ
完全:	いいえ

探索 > 深さ優先探索

深さ優先探索（ふかさゆうせんたんさく、英: 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 )

反復深化深さ優先探索

→詳細は「反復深化深さ優先探索」を参照

外部リンク