C++を使用してDFSトラバーサルを段階的に印刷するプログラム

このチュートリアルでは、特定の二分木で深さ優先探索を使用してトラバーサルのステップを印刷するプログラムについて説明します。

これには、バックトラッキング手順も含め、深さ優先探索で発生するすべてのステップが含まれます。

DFS中に、各ノードをトラバースし、同時に親ノードと使用されるエッジを格納します。トラバーサル中に隣接するエッジにアクセスした場合は、深さ優先探索のステップとして正確なノードを印刷できます。

例

#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
vector<int> adj[N];
//printing the steps in DFS traversal
void dfs_steps(int u, int node, bool visited[],
vector<pair<int, int< > path_used, int parent, int it){
   int c = 0;
   for (int i = 0; i < node; i++)
   if (visited[i])
      c++;
   if (c == node)
      return;
//marking the node as visited
   visited[u] = true;
   path_used.push_back({ parent, u });
   cout << u << " ";
   for (int x : adj[u]){
      if (!visited[x])
         dfs_steps(x, node, visited, path_used, u, it + 1);
   }
   for (auto y : path_used)
   if (y.second == u)
   dfs_steps(y.first, node, visited,
   path_used, u, it + 1);
}
void dfs(int node){
   bool visited[node];
   vector<pair<int, int> > path_used;
   for (int i = 0; i < node; i++)
   visited[i] = false;
   dfs_steps(0, node, visited, path_used, -1, 0);
   }
void add_edge(int u, int v){
   adj[u].push_back(v);
   adj[v].push_back(u);
}
int main(){
   int node = 11, edge = 13;
   add_edge(0, 1);
   add_edge(0, 2);
   add_edge(1, 5);
   add_edge(1, 6);
   add_edge(2, 4);
   add_edge(2, 9);
   add_edge(6, 7);
   add_edge(6, 8);
   add_edge(7, 8);
   add_edge(2, 3);
   add_edge(3, 9);
   add_edge(3, 10);
   add_edge(9, 10);
   dfs(node);
   return 0;
}

出力

0 1 5 1 6 7 8 7 6 1 0 2 4 2 9 3 10