程序使用C ++逐步打印DFS遍历

在本教程中，我们将讨论一个程序，该程序将在给定的二叉树中使用“深度优先搜索”来打印遍历的步骤。

这将包括在深度优先搜索中发生的每个步骤，包括回溯过程。

在DFS期间，我们将遍历每个节点，同时存储父节点和使用的边。在遍历期间，如果已经访问了相邻的边缘，则可以将精确的节点作为深度优先搜索中的步骤进行打印。

示例

#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
vector<int> adj[N];
//在DFS遍历中打印步骤
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;
//将节点标记为已访问
   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