โปรแกรม C++ พิมพ์ขั้นตอนการท่องลึก (DFS) แบบขั้นตอน

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมพิมพ์ขั้นตอนของการท่องโดยใช้การค้นหาแบบลึก (Depth First Search) ในต้นไม้ไบนารีที่กำหนด

สิ่งนี้จะรวมทุกขั้นตอนที่เกิดขึ้นในการค้นหาแบบลึก รวมถึงกระบวนการย้อนกลับ (backtracking) ด้วย

ระหว่าง DFS เราจะท่องแต่ละโหนดและเก็บโหนดพาเรนต์และขอบที่ใช้ไว้พร้อมกัน ระหว่างการท่อง ถ้าขอบที่อยู่ติดกันเคยถูกเยี่ยมชมแล้ว โหนดที่แน่นอนนั้นสามารถพิมพ์เป็นขั้นตอนในการค้นหาแบบลึกได้

ตัวอย่าง

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

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

// พิมพ์ขั้นตอนในการท่อง DFS
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; 
}

ผลลัพธ์

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