深さ優先探索

コンピュータサイエンスにおいて、深さ優先探索（DFS）は、ツリー構造やグラフ構造などのデータ構造を走査または探索するためのアルゴリズムです。このアルゴリズムは、ルートノード（グラフの場合は任意のノードをルートノードとして選択）から開始し、各ブランチに沿って可能な限り探索を進めてから、必要に応じてバックトラックします。グラフのバックトラックを支援するため、指定されたブランチに沿ってこれまでに発見されたノードを追跡するために、通常はスタックなどの追加メモリが必要となります。

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

物件

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

人工知能における解の探索やウェブクローリングなど、特定のドメインに関連する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 に到達することはありません。

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

深さ優先探索の出力

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

頂点順序付け

深さ優先探索を用いて、グラフや木の頂点を線形に順序付けることも可能です。これには4つの方法があります。

先行順序付けとは、深さ優先探索アルゴリズムによって最初に訪問された順序で頂点を並べたリストです。これは、この記事の前半で説明したように、探索の進行状況を簡潔かつ自然に記述する方法です。式木の先行順序付けは、ポーランド記法では次の式で表されます。
後順とは、アルゴリズムが最後に訪問した順序で頂点を並べたリストのことです。式木の後順とは、逆ポーランド記法で表された式のことです。
逆順順序付けとは、順順序付けの逆、つまり、頂点を最初に訪れた順序とは逆の順序で並べたリストのことです。逆順順序付けは、後順順序付けとは異なります。
逆後順とは、後順の逆、つまり最後に訪れた順序とは逆の順序で頂点を並べたリストのことです。逆後順は前順とは異なります。

二分木には、さらに順序付けと逆順序付けがあります。

例えば、以下の有向グラフをノード A から探索する場合、走査の順序は ABDBACA または ACDCABA のいずれかになります (A から B または C のどちらを先に訪問するかはアルゴリズムによります)。ここで注意すべきは、ノードにまだ訪問していない隣接ノードがあるかどうかを確認するために、ノードにバックトラックして再度訪問する場合も含まれるということです (隣接ノードがないことが判明した場合でも)。したがって、可能な前順は ABDC と ACDB、可能な後順は DBCA と DCBA、可能な逆後順は ACBD と ABC D となります。

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

( A )ならば{ B } それ以外 { C } D

擬似コード

0

1

前のノード再起動開始

対話型深さ優先探索デモンストレーション

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

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

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

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

辺AB、BD、BF、FE、AC、CG、AEを持つ無向グラフ — 上記からコピーした例のグラフ

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

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

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

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

反復深さ優先探索の別の実装方法として、ノードのスタックの代わりに、ノードの近傍のリストのイテレータのスタックを使用する方法がある。これにより、再帰的DFSと同じ走査が得られる。 ^{[ 8 ]}

手続きDFS_iterative( G , v )は、Sをスタックと する。vを発見済みとして ラベル付けするS .push(iterator of G .adjacentEdges( v )) Sが空でない間、次の処理を実行するS .peek().hasNext()があればw = S .peek().next() wが発見済みとしてラベル付けされていない場合は、 w を発見済みとして ラベル付けするS .push(iterator of G .adjacentEdges( w )) else S .pop()

アプリケーション

迷路生成に用いられる深さ優先探索に類似したランダム化アルゴリズム。

深さ優先探索を構成要素として用いるアルゴリズムには、以下のようなものがある。

連結成分の検出。
トポロジカルソート。
2つの（辺または頂点）で連結された成分を見つける。
3つの（辺または頂点）で連結された成分を見つける。
グラフの橋を見つける。
グループの極限集合をプロットするために単語を生成する。
強く連結した成分を見つける。
系統樹において、ある種が他の種に近いかどうかを判断すること。
平面度テスト。^{[ 9 ]}^{[ 10 ]}
迷路のように解が一つしかないパズルを解く。（深さ優先探索（DFS）は、現在の経路上のノードのみを訪問済みノードセットに含めることで、迷路のすべての解を見つけるように応用できる。）
迷路生成には、ランダム化DFSが使用される場合がある。
グラフにおける双連結性の検出。
コモンウェルス王国が共有する王位継承。^{[ 11 ]}

複雑

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

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

注記

↑シャルル・ピエール・トレモー（1859–1882）パリ工科大学（X:1876）、フランスの電信技師。2010年12月2日、マコンアカデミー（ブルゴーニュ地方、フランス）にてジャン・ペルティエ＝ティベール教授による公開講演。（抄録は2011年3月、学術年報に掲載 – ISSN 0980-6032）
↑ Even, Shimon (2011), Graph Algorithms (2nd ed.), Cambridge University Press, pp. 46–48 , ISBN 978-0-521-73653-4。
↑セッジウィック、ロバート (2002)、C++ のアルゴリズム: グラフアルゴリズム(第 3版)、ピアソン教育、ISBN 978-0-201-36118-6。
↑コーメン、トーマス H.、チャールズ E. ライザーソン、ロナルド L. リベスト。 p.606
↑グッドリッチとタマッシア。コーメン、ライザーソン、リベスト、スタイン
↑ 93ページ、『アルゴリズム設計』、クラインバーグとタルドス
↑ "スタックベースのグラフ走査 ≠ 深さ優先探索" . 11011110.github.io . 2020年6月10日取得.
↑セッジウィック、ロバート（2010）。『Javaによるアルゴリズム』アディソン・ウェスリー。ISBN 978-0-201-36121-6OCLC 837386973
↑ Hopcroft, John ; Tarjan, Robert E. (1974), "Efficient planarity testing" (PDF) , Journal of the Association for Computing Machinery , 21 (4): 549– 568, doi : 10.1145/321850.321852 , hdl : 1813/6011 , S2CID 6279825 。
↑ de Fraysseix, H.; Ossona de Mendez, P. ; Rosenstiehl, P. (2006), "Trémaux Trees and Planarity", International Journal of Foundations of Computer Science , 17 (5): 1017– 1030, arXiv : math/0610935 , Bibcode : 2006math.....10935D , doi : 10.1142/S0129054106004248 , S2CID 40107560 。
↑ Baccelli, Francois; Haji-Mirsadeghi, Mir-Omid; Khezeli, Ali (2018), "Eternal family trees and dynamics on unimodular random graphs", in Sobieczky, Florian (ed.), Unimodularity in Randomly Generated Graphs: AMS Special Session, October 8–9, 2016, Denver, Colorado , Contemporary Mathematics, vol. 719, Providence, Rhode Island: American Mathematical Society, pp. 85– 127, arXiv : 1608.05940 , doi : 10.1090/conm/719/14471 , ISBN 978-1-4704-3914-9MR 3880014、S2CID 119173820 例3.7、93ページを参照。
↑ Reif, John H. (1985). "深さ優先探索は本質的に逐次的である". Information Processing Letters . 20 (5): 229–234 . doi : 10.1016/0020-0190(85)90024-9 .
↑ Mehlhorn, Kurt ; Sanders, Peter (2008). Algorithms and Data Structures: The Basic Toolbox (PDF) . Springer. 2015年9月8日にオリジナルからアーカイブされたPDF 。
↑ Aggarwal, A.; Anderson, RJ (1988)、「深さ優先探索のためのランダムNCアルゴリズム」、 Combinatorica、8 (1): 1– 12、doi : 10.1007/BF02122548、MR 0951989、S2CID 29440871 。
↑カーガー、デヴィッド R. ; Motwani、Rajeev (1997)、「最小カットのためのNCアルゴリズム」、 SIAM Journal on Computing、26 (1): 255–272、CiteSeerX 10.1.1.33.1701、doi : 10.1137/S0097539794273083、MR 1431256 。

参考文献

Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein。『アルゴリズム入門』第2版。MIT PressおよびMcGraw-Hill、2001年。ISBN 0-262-03293-7セクション 22.3: 深さ優先探索、pp. 540–549。
グッドリッチ、マイケル・T.、タマシア、ロベルト（2001）、『アルゴリズム設計：基礎、分析、インターネットの例』、ワイリー、ISBN 0-471-38365-1
ジョン・クラインバーグ; Tardos、Éva ( 2006)、アルゴリズム設計、Addison Wesley、 92–94ページ
クヌース、ドナルド・E. (1997)、『コンピュータプログラミングの技法』第1巻、第3版、ボストン：アディソン・ウェスリー、ISBN 0-201-89683-4OCLC 155842391、2008年9月4日にオリジナルからアーカイブ、2008年2月12日に取得

外部リンク

オープンデータ構造 - セクション 12.3.2 - 深さ優先探索、パット・モリン
C++ Boost Graphライブラリ：深さ優先探索
深さ優先探索のアニメーション（有向グラフの場合）
深さ優先探索と幅優先探索：解説とコード
深さ優先探索アルゴリズムの図解解説（JavaおよびC++による実装例）
YAGSBPL – グラフ探索とプランニングのためのテンプレートベースのC++ライブラリ
深さ優先探索の可視化

[1] シャルル・ピエール・トレモー（1859–1882）パリ工科大学（X:1876）、フランスの電信技師。2010年12月2日、マコンアカデミー（ブルゴーニュ地方、フランス）にてジャン・ペルティエ＝ティベール教授による公開講演。（抄録は2011年3月、学術年報に掲載 – ISSN 0980-6032）

[2] Even, Shimon (2011), Graph Algorithms (2nd ed.), Cambridge University Press, pp. 46–48 , ISBN 978-0-521-73653-4。

[3] セッジウィック、ロバート (2002)、C++ のアルゴリズム: グラフアルゴリズム(第 3版)、ピアソン教育、ISBN 978-0-201-36118-6。

[4] コーメン、トーマス H.、チャールズ E. ライザーソン、ロナルド L. リベスト。 p.606

[5] グッドリッチとタマッシア。コーメン、ライザーソン、リベスト、スタイン

[6] 93ページ、『アルゴリズム設計』、クラインバーグとタルドス

[7] "スタックベースのグラフ走査 ≠ 深さ優先探索" . 11011110.github.io . 2020年6月10日取得.

[8] セッジウィック、ロバート（2010）。『Javaによるアルゴリズム』アディソン・ウェスリー。ISBN 978-0-201-36121-6OCLC 837386973

[9] Hopcroft, John ; Tarjan, Robert E. (1974), "Efficient planarity testing" (PDF) , Journal of the Association for Computing Machinery , 21 (4): 549– 568, doi : 10.1145/321850.321852 , hdl : 1813/6011 , S2CID 6279825 。

[10] Fraysseix, H.; Ossona de Mendez, P. ; Rosenstiehl, P. (2006), "Trémaux Trees and Planarity", International Journal of Foundations of Computer Science , 17 (5): 1017– 1030, arXiv : math/0610935 , Bibcode : 2006math.....10935D , doi : 10.1142/S0129054106004248 , S2CID 40107560 。

[11] Baccelli, Francois; Haji-Mirsadeghi, Mir-Omid; Khezeli, Ali (2018), "Eternal family trees and dynamics on unimodular random graphs", in Sobieczky, Florian (ed.), Unimodularity in Randomly Generated Graphs: AMS Special Session, October 8–9, 2016, Denver, Colorado , Contemporary Mathematics, vol. 719, Providence, Rhode Island: American Mathematical Society, pp. 85– 127, arXiv : 1608.05940 , doi : 10.1090/conm/719/14471 , ISBN 978-1-4704-3914-9MR 3880014、S2CID 119173820 例3.7、93ページを参照。

[12] Reif, John H. (1985). "深さ優先探索は本質的に逐次的である". Information Processing Letters . 20 (5): 229–234 . doi : 10.1016/0020-0190(85)90024-9 .

[mehlhorn-13] Mehlhorn, Kurt ; Sanders, Peter (2008). Algorithms and Data Structures: The Basic Toolbox (PDF) . Springer. 2015年9月8日にオリジナルからアーカイブされたPDF 。

[14] Aggarwal, A.; Anderson, RJ (1988)、「深さ優先探索のためのランダムNCアルゴリズム」、 Combinatorica、8 (1): 1– 12、doi : 10.1007/BF02122548、MR 0951989、S2CID 29440871 。

[15] カーガー、デヴィッド R. ; Motwani、Rajeev (1997)、「最小カットのためのNCアルゴリズム」、 SIAM Journal on Computing、26 (1): 255–272、CiteSeerX 10.1.1.33.1701、doi : 10.1137/S0097539794273083、MR 1431256 。

[ 1 ]

[ 2 ]

[ 3 ]

4

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]。

[ 13 ]

[ 14 ]

[ 15 ]

深さ優先探索

物件

例

深さ優先探索の出力

頂点順序付け

擬似コード

アプリケーション

複雑

関連項目

注記

参考文献

外部リンク

関連するトピック

コンピュータサイエンス

ツリー構造

グラフ

アルゴリズムです。このアルゴリズムは、