深さ優先探索

ウィキペディア

深さ優先探索

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/05/07 14:28 UTC 版)

探索 > 深さ優先探索

深さ優先探索
探索順
一般的な情報
分類: 探索アルゴリズム データ構造: グラフ 時間計算量: $O(|E|)$ 深さ優先探索のイメージ 深さ優先探索（ふかさゆうせんたんさく、英: 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頂点間の経路を探す例。なお、これを幅優先探索でやると、辺の重みなしの最短経路問題になる。 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 ) 関連項目 深さ制限探索 幅優先探索 外部リンク 『深さ優先探索と幅優先探索』 - 高校数学の美しい物語 Depth-First Search Animation (for a directed graph) Another Depth-First Search Animation (for a directed graph - recursive)

ウィキペディア小見出し辞書

深さ優先探索

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/29 13:54 UTC 版)

「二分木」の記事における「深さ優先探索」の解説

奥優先探索ともいう。根からできるだけ遠く、しかも、既に調べたノードの子であるノードから調べていく方法である。一般のグラフと異なりこれまでに訪れたノードを全て記憶しておく必要はない。というのも木には閉路がないからである。行きがけ順、通りがけ順、帰りがけ順探索はすべてこれの特殊な例である。

Weblio日本語例文用例辞書

「深さ優先探索」の例文・使い方・用例・文例

• 深さ優先探索という,人工知能における探索手法