Depth-first searchとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > Depth-first searchの意味・解説 

深さ優先探索

(Depth-first search から転送)

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

探索 > 深さ優先探索
深さ優先探索

探索順
一般的な情報
分類: 探索アルゴリズム
データ構造: グラフ
時間計算量:
深さ優先探索のイメージ

深さ優先探索(ふかさゆうせんたんさく、: 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 )

反復深化深さ優先探索

関連項目

外部リンク




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「Depth-first search」の関連用語

Depth-first searchのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



Depth-first searchのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの深さ優先探索 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS