C++ प्रोग्राम: DFS ट्रैवर्सल को चरण-दर-चरण प्रिंट करना

इस ट्यूटोरियल में, हम दिए गए बाइनरी ट्री में डेप्थ फर्स्ट सर्च का उपयोग करके ट्रैवर्सल के चरणों को प्रिंट करने के प्रोग्राम पर चर्चा करेंगे।

इसमें डेप्थ-फर्स्ट सर्च में होने वाला हर चरण शामिल होगा जिसमें बैकट्रैकिंग प्रक्रिया भी शामिल है।

DFS के दौरान, हम प्रत्येक नोड को पार करेंगे और साथ ही पैरेंट नोड और उपयोग किए गए एज को स्टोर करेंगे। ट्रैवर्सल के दौरान, यदि आसन्न एज देखा गया है, तो सटीक नोड को डेप्थ-फर्स्ट सर्च में एक चरण के रूप में प्रिंट किया जा सकता है।

उदाहरण

#include <bits/stdc++.h>
using namespace std;

const int N = 1000;
vector adj[N];

// DFS ट्रैवर्सल में चरण प्रिंट करना
void dfs_steps(int u, int node, bool visited[], vector> 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> 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