इस ट्यूटोरियल में, हम किसी दिए गए बाइनरी ट्री में डेप्थ फर्स्ट सर्च का उपयोग करके ट्रैवर्सल के चरणों को प्रिंट करने के लिए एक प्रोग्राम पर चर्चा करेंगे।
इसमें हर चरण शामिल होगा जो गहराई से पहली खोज में होता है जिसमें बैकट्रैकिंग प्रक्रिया भी शामिल है।
डीएफएस के दौरान, हम प्रत्येक नोड का पता लगाएंगे और साथ ही साथ मूल नोड और उपयोग किए गए किनारे को संग्रहीत करेंगे। ट्रैवर्सल के दौरान, यदि आसन्न किनारे का दौरा किया गया है, तो सटीक नोड को गहराई-पहली खोज में एक चरण के रूप में मुद्रित किया जा सकता है।
उदाहरण
#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