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