深さ優先探索
深さ優先探索（ふかさゆうせんたんさく、英: depth-first search, DFS、バックトラック法ともいう）は、木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な限り探索を行う。「縦型探索」とも呼ばれる。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
幅優先探索と並ぶ基本的なグラフ走査のアルゴリズムです。
迷路を解くTrémaux’s algorithmが始まりと言われます。
深さ優先探索は、 まずは子のないノードに行き着くまで深く伸びていき、その後バックトラックして最も近くの探索の終わっていないノードまで戻ります。
計算量は、幅優先探索と同じく時間計算量\(O(|E|)\)空間計算量\(O(|V|)\)ですが、一般的な問題に対しては、深さ優先探索の方が空間計算量は小さいと言われます。
具体的に葉が全て埋まった高さ3の完全2分木を考えれば、葉は8個のノードを持つので、深さ優先探索で保持する最大のノード数は3、幅優先探索では8となり、深さ優先探索のほうが空間計算量は小さくなります。
このように2分木構造であれば、深さ優先探索は\(O( \log N)\)、幅優先探索は \(O( N)\)で、深さ優先探索の方が空間計算量は良くなります。
疑似コード
深さ優先探索には、スタックを用いる方法と再帰を用いる方法があります。
ただし、内部的に再帰はスタックを使い実行されるので、本質的には同じことになります。
スタックを用いるコード
LIFOのADTであるスタックを用います。
スタックから現在の頂点を取り出し、隣接する頂点が訪問済みかどうかを確認し、訪問していない場合はスタックに積みます。これをスタックが空になるまで繰り返します。
幅優先探索のキューをスタックにして、訪問済みフラグの更新タイミングを変更します。
function 深さ優先探索(v)
S ← 空のスタック
v を S に積む
while S が空ではない do
v ← S から取り出す
if v が未訪問 then
v に訪問済みの印を付ける
v を処理する
for each v に接続している頂点 i do
if i が未訪問 then
i を S に積む
再帰を用いるコード
コードとしてこちらの方が単純です。
function 深さ優先探索(v)
v に訪問済みの印を付ける
v を処理する
for each v に接続している頂点 i do
if i が未訪問 then
深さ優先探索(i)
探索の順番は以下のようになります。
隣接しているノードにどんどんと進んでいき、進めくなったら進める分岐のあるノードまで後戻りして（後戻りのことを’back-track’と言います）、また進めなくなるまで進みます。
深さ優先探索の応用例
閉路の検出
深さ優先探索で親ノードへの戻り辺があれば、それは閉路である。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
Kosaraju’s algorithm
In computer science, Kosaraju’s algorithm (also known as the Kosaraju–Sharir algorithm) is a linear timealgorithm to find the strongly connected components of a directed graph.
From Wikipedia, the free encyclopedia
トポロジカルソート
トポロジカルソート（英: topological sort）とは、グラフ理論において、有向非巡回グラフ（英: directed acyclic graph, DAG）の各ノードを順序付けして、どのノードもその出力辺の先のノードより前にくるように並べることである。有向非巡回グラフは必ずトポロジカルソートすることができる。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
