深さ優先探索のソースを表示

{{pathnav|探索|frame=1}}
{| class="infobox" style="margin-left: 0.5em; border:1px #aaa solid; border-collapse: collapse;"
! style="background-color: #ffc0c0; border:1px #aaa solid;" |  深さ優先探索
|-
| style="margin: 0 auto; text-align: center; font-size: smaller;"| [[ファイル:Depth-first-tree.png|none|300px|Order in which the nodes get expanded]]<br />探索順
|-
! style="background-color: #ffc0c0; border:1px #aaa solid;" | '''一般的な情報'''
|-
|
{| style="border: 0;" 
|-
| ''分類'': || [[探索|探索アルゴリズム]]
|-
| ''データ構造'': || [[グラフ (データ構造)|グラフ]]
|-
| ''時間計算量'': || <math>O(|E|)</math>
|-
| ''空間計算量'': || <math>O(|V|)</math>
|-
| ''最適'': || いいえ
|-
| ''完全'': || いいえ
|-
|}
|-
|}
[[ファイル:Depthfirst.png|thumb|right|200px|深さ優先探索のイメージ]]

'''深さ優先探索'''（ふかさゆうせんたんさく、{{lang-en-short|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頂点間の経路を探す例。なお、これを[[幅優先探索]]でやると、辺の重みなしの[[最短経路問題]]になる。
<syntaxhighlight lang="python">
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 )
</syntaxhighlight>

== 反復深化深さ優先探索 ==
{{main|反復深化深さ優先探索}}

== 関連項目 ==
* [[深さ制限探索]]
* [[幅優先探索]]

== 外部リンク ==
* {{高校数学の美しい物語|1247|深さ優先探索と幅優先探索}}
* [http://www.cs.duke.edu/csed/jawaa/DFSanim.html Depth-First Search Animation (for a directed graph)]
* [http://dima.jd-software.org/dfs/DFS.html Another Depth-First Search Animation (for a directed graph - recursive)]

{{アルゴリズム}}
{{DEFAULTSORT:ふかさゆうせんたんさく}}
[[Category:検索アルゴリズム]]
[[Category:組合せ最適化]]