Chương trình C++ in duyệt DFS cây nhị phân từng bước

In các bước duyệt DFS (tìm kiếm theo chiều sâu) trên cây nhị phân, bao gồm cả quá trình backtracking.

Trong DFS, duyệt từng nút và lưu nút cha và cạnh đã dùng. Nếu cạnh kề đã thăm thì in nút đó như một bước trong DFS.

Ví dụ mã nguồn

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

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

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;
}

Kết quả đầu ra

0 1 5 1 6 7 8 7 6 1 0 2 4 2 9 3 10