「深さ優先探索」の版間の差分
削除された内容 追加された内容
編集の要約なし タグ: モバイル編集 モバイルウェブ編集 |
m 182.171.128.248 (会話) による版を Abionab による版へ巻き戻し タグ: 巻き戻し |
||
1行目:
{{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での実装(再帰なし) ==
23 ⟶ 75行目:
stack.push( child )
</syntaxhighlight>
== 反復深化深さ優先探索 ==
{{main|反復深化深さ優先探索}}
== 関連項目 ==
28 ⟶ 83行目:
* [[幅優先探索]]
== 外部リンク ==
* [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)]
{{アルゴリズム}}
| |||