এই টিউটোরিয়ালে, আমরা একটি প্রদত্ত বাইনারি ট্রিতে ডেপথ ফার্স্ট সার্চ ব্যবহার করে ট্রাভার্সালের ধাপগুলি প্রিন্ট করার জন্য একটি প্রোগ্রাম নিয়ে আলোচনা করব৷
এটি ব্যাকট্র্যাকিং পদ্ধতি সহ গভীরতা-প্রথম অনুসন্ধানে ঘটে যাওয়া প্রতিটি পদক্ষেপ অন্তর্ভুক্ত করবে৷
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
