深さ優先探索

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
探索 > 深さ優先探索
深さ優先探索
Order in which the nodes get expanded

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

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

概要[編集]

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

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

メモリに載りきらないような大規模な木を探索する場合、深さ優先探索は探索木のパスの長さが長くなりすぎて探索が終わらないという問題を抱えている。「訪れたノードを記憶する」という単純な方法は、十分なメモリ量がない場合通用しなくなるのである。また、探索対象が木ではなく一般の有向グラフである場合(特に、ループを含む場合)にも同じ問題が起こる。これは、木の深さを段階的に増やして探索する反復深化深さ優先探索(en:iterative deepening depth-first search)と呼ばれるアルゴリズムで解決することができる。

下記の図を用いた場合、

Graph.traversal.example.png

グラフの左にある辺が右にある辺より先に選択され、以前訪れたノードを記憶することにより再訪しないとするならば、Aからスタートした深さ優先探索はA, B, D, F, E, C, Gという順番で訪れる。

ここで以前訪れたノードを記憶していない場合、A, B, D, F, E, A, B, D, F, Eと、A, B, D, F, Eのループに捕まって永遠にCやGに到達することはできない。

反復深化はこのループを回避し、上記のように左から右に探索が進むとすると、下記の深さにおいて下記のノードに到達する。

  • 0: A
  • 1: A (repeated), B, C, E

(反復深化はCをみつけていることに注意。通常の深さ優先探索では見つからない。)

  • 2: A, B, D, F, C, G, E, F

(以前Cを見つけていることに注意。Eを別のパスでみつけていることとFでループを見つけていることにも注意。)

  • 3: A, B, D, F, E, C, G, E, F, B

このグラフでは深さを増やしていくたびに、アルゴリズムが探索を断念して他の枝に行くまで"ABFE", "AEFB"のループが長くなる。

擬似コード[編集]

再帰あり[編集]

深さ優先探索(v)
    v に訪問済みの印を付ける
    v を処理する
    for each (v に接続していて かつ 未訪問の頂点 i)
        深さ優先探索(i)

再帰なし[編集]

深さ優先探索(v)
    S ← 空のスタック
    v に訪問済みの印を付ける
    v を S に積む
    while (S が空ではない)
        v ← S から取り出す
        v を処理する
        for each (v に接続していて かつ 未訪問の頂点 i)
            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 )

関連項目[編集]

外部リンク[編集]