ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมเพื่อพิมพ์ขั้นตอนของการข้ามผ่านโดยใช้ Depth First Search ในไบนารีทรีที่กำหนด
ซึ่งจะรวมถึงทุกขั้นตอนที่เกิดขึ้นในการค้นหาเชิงลึกก่อน รวมถึงขั้นตอนการย้อนรอยด้วย
ระหว่าง 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
