depth first search c program traverse graph
このチュートリアルでは、グラフまたはツリーが深さ方向にトラバースされるC ++の深さ優先探索（DFS）について説明します。また、DFSアルゴリズムと実装についても学習します。
深さ優先探索（DFS）は、ツリーまたはグラフをトラバースするために使用されるさらに別の手法です。
DFSは、ルートノードまたは開始ノードから開始し、グラフまたはツリーを深く掘り下げて、現在のノードの隣接ノードを探索します。これは、DFSでは、子のないノードが検出されるまで、ノードが深さ方向に探索されることを意味します。
リーフノードに到達すると、DFSはバックトラックし、同様の方法でさらにいくつかのノードの探索を開始します。
=> ここで初心者向けC ++トレーニングガイドに注意してください。
学習内容：
C ++での深さ優先探索（DFS）
ノードを幅方向に探索するBFSとは異なり、DFSではノードを深さ方向に探索します。 DFSでは、探索されるノードを格納するためにスタックデータ構造を使用します。未探索のノードにつながるエッジは「検出エッジ」と呼ばれ、すでにアクセスしたノードにつながるエッジは「ブロックエッジ」と呼ばれます。
次に、DFS手法のアルゴリズムと擬似コードを確認します。
DFSアルゴリズム
- ステップ1： ツリーまたはグラフのルートノードまたは開始ノードをスタックに挿入します。
- ステップ2： スタックから一番上のアイテムをポップし、訪問済みリストに追加します。
- ステップ3： 訪問済みとマークされたノードの隣接するすべてのノードを検索し、まだ訪問されていないノードをスタックに追加します。
- ステップ4 ：スタックが空になるまで、手順2と3を繰り返します。
擬似コード
DFSの擬似コードを以下に示します。
上記の擬似コードから、すべての頂点に確実にアクセスするために、DFSアルゴリズムが各頂点で再帰的に呼び出されていることがわかります。
イラスト付きトラバーサル
ここで、グラフのDFSトラバーサルについて説明します。わかりやすくするために、BFSの図で使用したのと同じグラフを使用します。
0を開始ノードまたはソースノードとします。まず、訪問済みとしてマークし、訪問済みリストに追加します。次に、スタック内の隣接するすべてのノードをプッシュします。
次に、隣接するノードの1つを処理します。つまり、スタックの最上位の1です。訪問済みリストに追加して、訪問済みとしてマークします。ここで、1の隣接ノードを探します。0はすでに訪問済みリストにあるため、無視して、スタックの最上位である2にアクセスします。
次に、ノード2を訪問済みとしてマークします。その隣接ノード4がスタックに追加されます。
次に、スタックの最上位である4を訪問済みとしてマークします。ノード4には、すでにアクセスされているノード2のみが隣接しているため、無視します。
この段階では、ノード3のみがスタックに存在します。その隣接ノード0はすでにアクセスされているため、無視します。ここで、3を訪問済みとしてマークします。
これでスタックは空になり、訪問済みリストには、指定されたグラフの深さ優先走査のシーケンスが表示されます。
与えられたグラフとトラバーサルシーケンスを観察すると、DFSアルゴリズムの場合、実際にグラフを深さ方向にトラバースしてから、もう一度バックトラックして新しいノードを探索していることがわかります。
深さ優先探索の実装
C ++を使用してDFSトラバーサル手法を実装しましょう。
#include #include using namespace std; //graph class for DFS travesal class DFSGraph { int V; // No. of vertices list *adjList; // adjacency list void DFS_util(int v, bool visited()); // A function used by DFS public: // class Constructor DFSGraph(int V) { this->V = V; adjList = new list(V); } // function to add an edge to graph void addEdge(int v, int w){ adjList(v).push_back(w); // Add w to v’s list. } void DFS(); // DFS traversal function }; void DFSGraph::DFS_util(int v, bool visited()) { // current node v is visited visited(v) = true; cout << v << ' '; // recursively process all the adjacent vertices of the node list::iterator i; for(i = adjList(v).begin(); i != adjList(v).end(); ++i) if(!visited(*i)) DFS_util(*i, visited); } // DFS traversal void DFSGraph::DFS() { // initially none of the vertices are visited bool *visited = new bool(V); for (int i = 0; i < V; i++) visited(i) = false; // explore the vertices one by one by recursively calling DFS_util for (int i = 0; i < V; i++) if (visited(i) == false) DFS_util(i, visited); } int main() { // Create a graph DFSGraph gdfs(5); gdfs.addEdge(0, 1); gdfs.addEdge(0, 2); gdfs.addEdge(0, 3); gdfs.addEdge(1, 2); gdfs.addEdge(2, 4); gdfs.addEdge(3, 3); gdfs.addEdge(4, 4); cout << 'Depth-first traversal for the given graph:'< 出力：
指定されたグラフの深さ優先走査：
0 1 2 4 3
説明のために使用したプログラムで、グラフをもう一度使用しました。すべての頂点に確実にアクセスするために、グラフの各頂点でDFSアルゴリズム（2つの関数に分離）が再帰的に呼び出されていることがわかります。
ランタイム分析
DFSの時間計算量は、BFSと同じです。 O（| V | + | E |） ここで、Vは頂点の数、Eは特定のグラフのエッジの数です。
BFSと同様に、グラフがほとんど入力されていないか、密に入力されているかに応じて、時間計算量の計算では、支配的な要素はそれぞれ頂点またはエッジになります。
反復DFS
上記のDFS手法の実装は本質的に再帰的であり、関数呼び出しスタックを使用します。 DFSを実装するための別のバリエーションがあります。 反復深さ優先探索 」。ここでは、明示的なスタックを使用して、訪問した頂点を保持します。
反復DFSの実装を以下に示します。実装は、キューの代わりにスタックデータ構造を使用するという点を除いて、BFSと同じであることに注意してください。
#include using namespace std; // graph class class Graph { int V; // No. of vertices list *adjList; // adjacency lists public: Graph(int V) //graph Constructor { this->V = V; adjList = new list(V); } void addEdge(int v, int w) // add an edge to graph { adjList(v).push_back(w); // Add w to v’s list. } void DFS(); // DFS traversal // utility function called by DFS void DFSUtil(int s, vector &visited); }; //traverses all not visited vertices reachable from start node s void Graph::DFSUtil(int s, vector &visited) { // stack for DFS stack dfsstack; // current source node inside stack dfsstack.push(s); while (!dfsstack.empty()) { // Pop a vertex s = dfsstack.top(); dfsstack.pop(); // display the item or node only if its not visited if (!visited(s)) { cout << s << ' '; visited(s) = true; } // explore all adjacent vertices of popped vertex. //Push the vertex to the stack if still not visited for (auto i = adjList(s).begin(); i != adjList(s).end(); ++i) if (!visited(*i)) dfsstack.push(*i); } } // DFS void Graph::DFS() { // initially all vertices are not visited vector visited(V, false); for (int i = 0; i < V; i++) if (!visited(i)) DFSUtil(i, visited); } //main program int main() { Graph gidfs(5); //create graph gidfs.addEdge(0, 1); gidfs.addEdge(0, 2); gidfs.addEdge(0, 3); gidfs.addEdge(1, 2); gidfs.addEdge(2, 4); gidfs.addEdge(3, 3); gidfs.addEdge(4, 4); cout << 'Output of Iterative Depth-first traversal:
'; gidfs.DFS(); return 0; } 出力：
反復深さ優先走査の出力：
0 3 2 4 1
再帰的な実装で使用したのと同じグラフを使用します。出力の違いは、反復実装でスタックを使用するためです。スタックはLIFOの順序に従うため、DFSのシーケンスが異なります。同じシーケンスを取得するには、頂点を逆の順序で挿入することをお勧めします。
BFSとDFS
これまで、グラフのトラバーサル手法、つまりBFSとDFSの両方について説明してきました。
次に、2つの違いを調べてみましょう。
BFS DFS 「幅優先探索」の略 「深さ優先探索」の略 ノードは、レベルごとに幅ごとに探索されます。 ノードは、リーフノードのみが存在するまで深さ方向に探索され、その後、他の未訪問ノードを探索するためにバックトラックされます。 BFSは、キューのデータ構造を利用して実行されます。 DFSは、スタックデータ構造を利用して実行されます。 パフォーマンスが低下します。 BFSよりも高速です。 2つのノード間の最短パスを見つけるのに役立ちます。 主にグラフのサイクルを検出するために使用されます。
DFSのアプリケーション
- グラフ内のサイクルの検出： グラフでDFSを実行しているときにバックエッジが見つかった場合、グラフにはサイクルがあると結論付けることができます。したがって、DFSはグラフ内のサイクルを検出するために使用されます。
- パスファインディング： 2つの頂点xとyが与えられると、DFSを使用してxとyの間のパスを見つけることができます。頂点xから始めて、yに遭遇するまで、スタックに向かう途中のすべての頂点をプッシュします。スタックの内容は、xとyの間のパスを示します。
- 最小スパニングツリーと最短パス： 重み付けされていないグラフのDFSトラバーサルにより、最小スパニングツリーとノード間の最短パスが得られます。
- トポロジカルソート： ジョブ間の特定の依存関係からジョブをスケジュールする必要がある場合は、トポロジカルソートを使用します。コンピュータサイエンスの分野では、主にリンカーのシンボル依存関係の解決、データのシリアル化、命令スケジューリングなどに使用されます。DFSはトポロジカルソートで広く使用されています。
結論
最後の数回のチュートリアルでは、グラフの2つのトラバーサル手法（BFSとDFS）について詳しく説明しました。両方の手法の違いとアプリケーションを確認しました。 BFSとDFSは基本的に、グラフのすべてのノードにアクセスするという同じ結果を達成しますが、出力の順序と実行方法が異なります。
また、両方の手法の実装も確認しました。 BFSはキューを使用しますが、DFSはスタックを使用してこの手法を実装します。これで、グラフのトラバーサル手法に関するチュートリアルを終了します。ツリーでBFSとDFSを使用することもできます。
ヘルプデスクサポート面接の質問と回答
次のチュートリアルでは、スパニングツリーとグラフのノード間の最短経路を見つけるためのいくつかのアルゴリズムについて詳しく学習します。
=> 完全なC ++チュートリアルリストについては、こちらをご覧ください。
推奨読書