深さ優先探索

深さ優先探索

ノードを訪問する順序
クラス	検索アルゴリズム
データ構造	グラフ
最悪の場合の パフォーマンス	${\displaystyle O(|V|+|E|)}$明示的グラフは繰り返しなしで走査され、暗黙的グラフは分岐係数bで深さdまで探索される${\displaystyle O(b^{d})}$
最悪の場合の 空間複雑度	${\displaystyle O(|V|)}$グラフ全体を繰り返しなしで走査する場合、重複ノードの除去を行わない暗黙のグラフではO(検索される最長パス長) = ${\displaystyle O(bd)}$
最適	いいえ（通常は最短経路を見つけません）

深さ優先探索( DFS ) は、ツリーまたはグラフデータ構造をトラバースまたは検索するためのアルゴリズムです。このアルゴリズムはルート ノード(グラフの場合は任意のノードをルート ノードとして選択) から開始し、バックトラックする前に各ブランチに沿って可能な限り探索します。指定されたブランチに沿ってこれまでに検出されたノードを追跡するには、通常はスタックなどの追加のメモリが必要であり、これはグラフのバックトラックに役立ちます。

深さ優先探索の一種は、19世紀にフランスの数学者シャルル・ピエール・トレモー^{[1]によって}迷路を解く戦略として研究されました。^{[2] [3]}

DFS の時間と空間の解析は、その応用分野によって異なります。理論計算機科学では、DFS は通常グラフ全体を走査するために使用され、時間がかかります[ ^4] 。ここで、 は頂点の数で 、辺の数 です。これはグラフのサイズに比例します。これらのアプリケーションでは、最悪の場合、現在の検索パス上の頂点のスタックと、すでに訪問した頂点のセットを格納するために空間も使用されます。したがって、この設定では、時間と空間の境界は幅優先探索と同じであり、これら 2 つのアルゴリズムのどちらを使用するかの選択は、複雑さよりも、2 つのアルゴリズムが生成する頂点の順序付けの異なる特性に依存します。 ${\displaystyle O(|V|+|E|)}$${\displaystyle |V|}$${\displaystyle |E|}$${\displaystyle O(|V|)}$

人工知能やウェブクローリングにおけるソリューションの検索など、特定のドメインに関連した DFS のアプリケーションでは、トラバースするグラフが大きすぎて全体を訪問できないか、無限大であることがよくあります (DFS は非終了の問題を抱える場合があります)。このような場合、検索は限られた深さまでしか実行されません。メモリやディスク容量などのリソースが限られているため、通常、以前に訪問したすべての頂点のセットを追跡するためのデータ構造は使用されません。検索が限られた深さまで実行される場合、時間は拡張された頂点と辺の数に関して依然として線形です (ただし、この数はグラフ全体のサイズと同じではありません。頂点の中には複数回検索されるものもあれば、まったく検索されないものもあるためです)。ただし、この DFS のバリアントの空間計算量は深さの制限に比例するだけなので、結果として、幅優先検索を使用して同じ深さを検索するために必要な空間よりもはるかに小さくなります。このようなアプリケーションでは、DFS は、可能性のあるブランチを選択するためのヒューリスティックな方法にもはるかに適しています。適切な深さ制限が事前にわからない場合、反復深化深さ優先探索は、制限が増加するシーケンスで DFS を繰り返し適用します。人工知能モードの分析では、分岐係数が1 より大きい場合、反復深化により、レベルあたりのノード数が幾何学的に増加するため、正しい深さ制限がわかっている場合に比べて実行時間が一定係数だけ増加します。

DFS はグラフ ノードのサンプルを収集するためにも使用できます。ただし、不完全な DFS は、不完全なBFSと同様に、次数の高いノードに偏っています。

次のグラフの場合:

ノード A から始まる深さ優先探索では、示されているグラフの左エッジが右エッジよりも先に選択され、探索が以前に訪れたノードを記憶していて繰り返さないと仮定すると (これは小さなグラフなので)、次の順序でノードを訪れます: A、B、D、F、E、C、G。この探索で横断されるエッジは、グラフ理論で重要な用途を持つ構造であるトレモー木を形成します。以前に訪れたノードを記憶せずに同じ探索を実行すると、A、B、D、F、E、A、B、D、F、E などの順序でノードを永遠に訪れることになり、A、B、D、F、E サイクルに陥って C や G に到達できなくなります。

反復深化は、この無限ループを回避する 1 つの手法であり、すべてのノードに到達します。

グラフの深さ優先探索の結果は、探索中に到達した頂点の全域木として簡単に説明できます。この全域木に基づいて、元のグラフのエッジは、ツリーのノードからその子孫の 1 つを指す前方エッジ、ノードからその祖先の 1 つを指す後方エッジ、およびどちらにも属さない交差エッジの 3 つのクラスに分類できます。全域木自体に属するエッジであるツリーエッジは、前方エッジとは別に分類されることがあります。元のグラフが無向グラフである場合、そのすべてのエッジはツリー エッジまたは後方エッジです。

深さ優先探索を使用して、グラフまたはツリーの頂点を線形に順序付けることもできます。これを行うには、次の 4 つの方法があります。

• 事前順序付けは、深さ優先探索アルゴリズムによって最初に訪問された順序で頂点をリストしたものです。これは、この記事の前半で行ったように、検索の進行状況を記述する簡潔で自然な方法です。式ツリーの事前順序付けは、ポーランド記法の式です。
• ポストオーダーは、アルゴリズムによって最後に訪問された順序で頂点を並べたリストです。式ツリーのポストオーダーは、逆ポーランド記法の式です。
• 逆事前順序付けは事前順序付けの逆、つまり、最初の訪問の逆の順序で頂点のリストを作成します。逆事前順序付けは事後順序付けと同じではありません。
• 逆ポストオーダーはポストオーダーの逆、つまり、最後に訪れたときと逆の順序で頂点を並べたリストです。逆ポストオーダーはプレオーダーとは異なります。

二分木の場合、さらに、入順序付けと逆入順序付けがあります。

たとえば、ノード A から始まる以下の有向グラフを検索する場合、トラバーサルのシーケンスは ABDBACA または ACDCABA のいずれかになります (A から最初に B または C を訪問するかどうかはアルゴリズムによります)。ノードへのバックトラック形式での繰り返し訪問は、そのノードにまだ訪問していない隣接ノードがあるかどうかを確認するためにここに含まれることに注意してください (隣接ノードがないことが判明した場合も含む)。したがって、可能な事前順序付けは ABDC と ACDB、可能な事後順序付けは DBCA と DCBA、可能な逆事後順序付けは ACBD と ABC D です。

逆ポストオーダーは、任意の有向非巡回グラフの位相的ソートを生成します。この順序付けは、制御フローの自然な線形化を表すことが多いため、制御フロー解析にも役立ちます。上のグラフは、以下のコードフラグメントの制御フローを表している可能性があり、このコードを ABCD または ACBD の順序で考えるのは自然ですが、ABDC または ACD B の順序を使用するのは自然ではありません。

もし（A）ならば{
     B
} それ以外 {
    Ｃ
}
だ

DFSの再帰的実装: ^[5]

手順DFS( G , v )は、 Gにあるvから wへのすべての有向辺に対してv を発見済みとして
    
    ラベル付けします。adjacentEdges( v )は、頂点wが発見済みとしてラベル付けされていない場合は、
            再帰的に DFS( G , w )
を呼び出します。  
        

スタック上に重複頂点が存在する可能性のある、最悪の空間計算量を持つDFSの非再帰実装: ^[6]${\displaystyle O(|E|)}$

手順DFS_iterative( G , v )は、S をスタックとし
    、 Sが空でない場合にS .push( v )
    を
    実行し、 v = S .pop()
        を実行し、vが発見済みとしてラベル付けされていない場合は、 G .adjacentEdges( v )内のvからwへのすべてのエッジに対してvを発見済み
            としてラベル
            付けし、 S .push( w )
を実行します。 
            
                

DFS のこれら 2 つのバリエーションは、各頂点の隣接ノードを互いに逆の順序で訪問します。再帰バリエーションで訪問されるvの最初の隣接ノードは、隣接エッジのリストの最初のノードですが、反復バリエーションでは、最初に訪問される隣接ノードは、隣接エッジのリストの最後のノードです。再帰実装では、サンプル グラフのノードを次の順序で訪問します: A、B、D、F、E、C、G。非再帰実装では、ノードを次の順序で訪問します: A、E、F、B、D、C、G。

非再帰実装は幅優先探索に似ていますが、次の 2 つの点で異なります。

1. キューの代わりにスタックを使用し、
2. 頂点が追加される前にこのチェックを行うのではなく、頂点がスタックからポップされるまで、頂点が発見されたかどうかのチェックを遅らせます。

Gが木の場合、幅優先探索アルゴリズムのキューをスタックに置き換えると、深さ優先探索アルゴリズムが生成されます。一般的なグラフの場合、反復深さ優先探索実装のスタックをキューに置き換えると、やや非標準的ではありますが、幅優先探索アルゴリズムが生成されます。^[7]

反復深さ優先探索の別の実装では、ノードのスタックの代わりに、ノードの近傍リストの反復子のスタックを使用します。これにより、再帰DFSと同じトラバーサルが得られます。 ^[8]

手順DFS_iterative( G , v )はSをスタック
    とするv を発見済みとして
    
    ラベル付けするS .push( G .adjacentEdges( v ) の反復子)
     、 Sが空でない場合 、S .peek().hasNext()を実行し、w = S .peek().next() を
            実行し、 wが発見済みとしてラベル付けされていない場合、w を発見済みとして
                
                ラベル付けするS .push( G .adjacentEdges( w ) の反復子)、
        それ以外の場合はS .pop()

         
             
            

深さ優先探索を構成要素として使用するアルゴリズムには次のものがあります。

• 接続されたコンポーネントを検索します。
• トポロジカルソート。
• 2 つの (エッジまたは頂点) 接続コンポーネントを検索します。
• 3 つの (エッジまたは頂点) 接続コンポーネントを検索します。
• グラフのブリッジを見つける。
• グループの極限セットをプロットするための単語を生成します。
• 強く連結したコンポーネントを見つけます。
• ある種が系統樹の中でどの種に近いか、あるいは別の種に近いかを判断すること。
• 平面性試験^{[9] [10]}
• 迷路など、解が 1 つしかないパズルを解きます。(DFS は、訪問したセットに現在のパス上のノードのみを含めることで、迷路のすべての解を見つけるように適応できます。)
• 迷路生成ではランダム化 DFS が使用される場合があります。
• グラフ内の二重接続性を見つける。
• 英連邦王国による王位継承権の共有。^[11]

DFS の計算の複雑さは、 John Reifによって調査されました。より正確には、グラフ が与えられた場合、標準的な再帰 DFS アルゴリズムによって計算される順序を とします。この順序は、辞書式深さ優先探索順序と呼ばれます。John Reif は、グラフとソースが与えられた場合の辞書式深さ優先探索順序の計算の複雑さを検討しました。問題の決定バージョン(ある頂点u がこの順序である頂点vの前に現れるかどうかをテストする) はP完全であり、^{[12] は「}並列処理にとって悪夢」であることを意味します。^{[13] : 189}${\displaystyle G}$${\displaystyle O=(v_{1},\dots ,v_{n})}$

深さ優先探索順序（必ずしも辞書式順序ではない）は、複雑度クラスRNCのランダム化並列アルゴリズムによって計算できる。^{[14] 1997年時点では、深さ優先探索が複雑度クラス}NCの決定論的並列アルゴリズムによって構築できるかどうかは不明であった。^[15]

• ツリー トラバーサル(事前順序、イン オーダー、事後順序の深さ優先トラバーサルの詳細)
• 幅優先探索
• 反復深化深さ優先探索
• 検索ゲーム

ウィキメディア・コモンズには、深さ優先探索に関連するメディアがあります。

• オープン データ構造 - セクション 12.3.2 - 深さ優先探索、Pat Morin
• C++ Boost グラフ ライブラリ: 深さ優先探索
• 深さ優先探索アニメーション（有向グラフ用）
• 深さ優先探索と幅優先探索: 説明とコード
• 深さ優先探索アルゴリズムの図解説明 (Java および C++ 実装)
• YAGSBPL – グラフ検索と計画のためのテンプレートベースの C++ ライブラリ