Depth First Search(DFS)Algorithm

Depth first SearchまたはDepth first traversalは、グラフまたはツリーデータ構造のすべての頂点を検索するための再帰的アルゴリズムです。フォーカストラバーサルによってとり行われるすべてのノードのグラフにすることが出来ます。

深度第一探索アルゴリズム

標準のDFS実装では、グラフの各頂点を二つのカテゴリのいずれかに配置します。

アルゴリズムの目的は、サイクルを避けながら、各頂点を訪問済みとしてマークすることです。,

DFSアルゴリズムは次のように機能します。

深さ優先検索アルゴリズムが例でどのように機能するかを見てみましょう。 5つの頂点を持つ無向グラフを使用します。,

頂点0から始めます。DFSアルゴリズムは、それを訪問したリストに入れ、隣接するすべての頂点をスタックに入れることから始まります。

次に、スタックの一番上にある要素、つまり1を訪問し、その隣接するノードに移動します。すでに0が訪問されているので、代わりに2を訪問します。,

頂点2には、4の未訪問の隣接する頂点があるため、それをスタックの先頭に追加して訪問します。

最後の要素3にアクセスした後、未訪問の隣接ノードがないため、グラフの深さ優先トラバーサルが完了しました。,

DFSの擬似コードを以下に示します。 Init()関数では、すべてのノードでDFS関数を実行していることに注意してください。これは、グラフが二つの異なる切断された部分を持つ可能性があるため、すべての頂点を確実にカバーするために、すべてのノードでDFSアルゴリズムを実,

DFS(G, u) u.visited = true for each v ∈ G.Adj if v.visited == false DFS(G,v) init() { For each u ∈ G u.visited = false For each u ∈ G DFS(G, u)}

深さ優先検索アルゴリズムのコードを例として以下に示します。コードは単純化されており、他の詳細ではなくアルゴリズムに焦点を当てることができます。

DFSアルゴリズムの時間の複雑さは、O(V + E)の形式で表されます。Vはノードの数、Eはエッジの数です。

アルゴリズムのスペースの複雑さはO(V)です。,