数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会学
时尚研究
法律研究一个使用 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
更新日期：01-Nov-2019
399 次浏览
广告