algorithm
奥行き最初の検索
サーチ…
深度優先検索への紹介
深さ優先探索は、ツリーまたはグラフのデータ構造を走査または探索するためのアルゴリズムである。 1つはルートから始まり、バックトラッキングする前に各ブランチに沿って可能な限り探査します。 19世紀のフランス人の数学者Charles PierreTrémauxが迷路問題解決のための戦略として奥行き検索のバージョンを調査しました。
深度優先探索は、元の頂点から到達可能なすべての頂点を見つける体系的な方法です。幅優先検索と同様に、DFSは与えられたグラフの連結成分を横断し、スパニングツリーを定義します。深さ優先探索の基本的な考え方は、すべてのエッジを体系的に探索することです。必要に応じて別の頂点からやり直します。頂点を発見するとすぐに、DFSはその頂点から探索を開始します（BFSとは異なり、頂点をキューに配置して後で探索します）。
例を見てみましょう。このグラフを横断します：
次のルールに従ってグラフをトラバースします：
- ソースから始める。
- ノードは二度訪れません。
- 私たちがまだ訪れなかったノードは白く塗られています。
- 訪問したノードはすべて子ノードに行きませんでしたが、グレーで表示されます。
- 完全に横断されたノードは黒色に着色されます。
それを段階的に見てみましょう： 
1つの重要なキーワードを見ることができます。それは後退している 。あなたは見ることができます。 5-1はバッジと呼ばれます。これは、まだノード1で完了していないため、別のノードからノード1へ行くということは、グラフにサイクルがあることを意味します。 DFSでは、ある灰色のノードから別の灰色のノードに行くことができれば、グラフにはサイクルがあることがわかります。これは、グラフ内のサイクルを検出する方法の1つです。 ソースノードと訪問するノードの順序に応じて、サイクル内の任意のエッジをバックグラウンドとして見つけることができます。たとえば、最初に1から5になった場合、 2-1をバッジとして見つけました。
灰色のノードから白いノードへ行くために取るエッジはツリーエッジと呼ばれます 。私たちがツリーのエッジを保持して他のものを削除するだけであれば、 DFSツリーを取得します 。
無向グラフでは、すでに訪問したノードを訪問することができれば、これはバックグラウンドでなければなりません。しかし、有向グラフの場合、色をチェックする必要があります。 1つの灰色のノードから別の灰色のノードに行くことができる場合にのみ、これをバッジと呼びます。
DFSでは、各ノードのタイムスタンプを保持することもできます。これは、さまざまな方法で使用できます（Topological Sortなど）。
- ノードvが白からグレーに変わるとき、時間はd [v]に記録される。
- ノードvが灰色から黒色に変わると、時間はf [v]に記録されます。
ここで、 d []は発見時間を意味し 、 f []は終了時間を意味する。私たちのpesudo-codeは次のようになります：
Procedure DFS(G):
for each node u in V[G]
color[u] := white
parent[u] := NULL
end for
time := 0
for each node u in V[G]
if color[u] == white
DFS-Visit(u)
end if
end for
Procedure DFS-Visit(u):
color[u] := gray
time := time + 1
d[u] := time
for each node v adjacent to u
if color[v] == white
parent[v] := u
DFS-Visit(v)
end if
end for
color[u] := black
time := time + 1
f[u] := time
複雑：
各ノードとエッジは一度訪問されます。したがって、DFSの複雑さはO（V + E）です 。ここで、 Vはノードの数を表し、 Eはエッジの数を表します。
深さの最初の検索のアプリケーション：
- 無向グラフのすべてのペアの最短経路を見つける。
- グラフの周期を検出します。
- 経路発見。
- トポロジカルソート。
- グラフが二者であるかどうかをテストする。
- 強く接続されたコンポーネントを見つける。
- 1つの解決策でパズルを解く。
