深さ優先探索
Order in which the nodes get expanded
探索順
一般的な情報
分類:探索アルゴリズム
データ構造:グラフ
時間計算量: O ( 。 E 。 ) {\displaystyle O(|E|)}
空間計算量: O ( 。 V 。 ) {\displaystyle O(|V|)}
最適:いいえ
完全:いいえ
深さ優先探索のイメージ
深さ優先探索（ふかさゆうせんたんさく、英: depth-first search, DFS、バックトラック法ともいう）は、木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な限り探索を行う。「縦型探索」とも呼ばれる。 形式的には、深さ優先探索は、探索対象となる木の最初のノードから、目的のノードが見つかるか子のないノードに行き着くまで、深く伸びていく探索である。その後はバックトラックして、最も近くの探索の終わっていないノードまで戻る。非再帰的な実装では、新しく見つかったノードはスタックに貯める。 深さ優先探索の空間計算量は幅優先探索の空間計算量より最悪のケースでは同じだが一般的なケースではずっと小さい。また、探索の種類によっては、分岐を選択するためのヒューリスティックな方法にも向いている。両者の時間計算量は、最悪のケースではノード数とたどる辺の数の合計に比例する。 以下は、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 )
概要
擬似コード
再帰あり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での実装(再帰なし)
反復深化深さ優先探索詳細は「反復深化深さ優先探索」を参照
関連項目
深さ制限探索
幅優先探索
外部リンク
『深さ優先探索と幅優先探索』 - 高校数学の美しい物語
⇒Depth-First Search Animation (for a directed graph)
⇒Another Depth-First Search Animation (for a directed graph - recursive)
表
話
編
歴
アルゴリズム
ソート
比較ソート
バブルソート
選択ソート
挿入ソート
シェルソート
クイックソート
マージソート
ヒープソート
シェーカーソート
コムソート
ノームソート
図書館ソート
イントロソート
奇偶転置ソート
線形時間ソート
鳩の巣ソート
基数ソート
バケットソート
並行ソート
ソーティングネットワーク
バッチャー奇偶マージソート
シェアソート
非効率的
ボゴソート
ストゥージソート
グラフ
トポロジカルソート
探索
リスト
線形探索
二分探索
木・グラフ
幅優先探索
最良優先探索
均一コスト探索
A*
深さ優先探索
反復深化深さ優先探索
深さ制限探索
双方向探索
分枝限定法
ビームサーチ
文字列
クヌース?モリス?プラット法
ボイヤー-ムーア法
エイホ?コラシック法
ラビン-カープ法
Bitap法
最短経路問題
ダイクストラ法
ベルマン?フォード法
ワーシャル?フロイド法
最小全域木
プリム法
クラスカル法
最大フロー問題
最小カット問題
フォード・ファルカーソン法
エドモンズ・カープ法
線型計画問題
シンプレックス法
カーマーカー法
順序統計量
選択アルゴリズム
クイックセレクト
中央値の中央値
計算幾何学
凸包アルゴリズム
