Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để in các bước của việc truyền tải bằng cách sử dụng Tìm kiếm Đầu tiên Độ sâu trong một cây nhị phân nhất định.
Điều này sẽ bao gồm mọi bước xảy ra trong tìm kiếm theo chiều sâu bao gồm cả quy trình bẻ khóa ngược.
Trong DFS, chúng ta sẽ duyệt qua từng nút và đồng thời lưu trữ nút cha và cạnh được sử dụng. Trong quá trình duyệt, nếu cạnh liền kề đã được truy cập, thì nút chính xác có thể được in như một bước trong tìm kiếm theo chiều sâu.
Ví dụ
#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;
} Đầu ra
0 1 5 1 6 7 8 7 6 1 0 2 4 2 9 3 10