探索 > 深さ優先探索

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

深さ優先探索
Order in which the nodes get expanded
Order in which the nodes get expanded

探索順
一般的な情報
分類: 探索アルゴリズム
データ構造: グラフ
時間計算量:
空間計算量:
最適: いいえ
完全: いいえ
深さ優先探索のイメージ

概要

編集

形式的には、深さ優先探索は、探索対象となる木の最初のノードから、目的のノードが見つかるか子のないノードに行き着くまで、深く伸びていく探索である。その後はバックトラックして、最も近くの探索の終わっていないノードまで戻る。非再帰的な実装では、新しく見つかったノードはスタックに貯める。

深さ優先探索の空間計算量は幅優先探索空間計算量より最悪のケースでは同じだが一般的なケースではずっと小さい。また、探索の種類によっては、分岐を選択するためのヒューリスティックな方法にも向いている。両者の時間計算量は、最悪のケースではノード数とたどる辺の数の合計に比例する。

擬似コード

編集

再帰あり

編集
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 )

反復深化深さ優先探索

編集

関連項目

編集

外部リンク

編集