C++ Program: Find All Forward Edges in a Directed Graph (DFS Classification)

Forward Edge ใน DFS Tree ของ Directed Graph คือ Edge (u, v) ที่ v เป็น Descendant ของ u ใน DFS Tree แต่ไม่ใช่ Tree Edge (คือ u → v โดย v ถูก Visit แล้ว และอยู่ใน Subtree ของ u)

Edge Classification ใน DFS

Algorithm: DFS with Timestamps

1. Track discovery[u] และ finish[u] Time
2. Color: WHITE (0), GRAY (1), BLACK (2)
3. Edge (u,v) เป็น Forward Edge ถ้า: color[v] == BLACK && discovery[u] < discovery[v]

โค้ด C++ (Clean Implementation)

#include <iostream>
#include <vector>
#include <string>
using namespace std;

enum Color { WHITE = 0, GRAY = 1, BLACK = 2 };

struct Graph {
    int V;
    vector> adj;
    vector color;
    vector discovery, finish;
    int time = 0;
    vector> forwardEdges;
    
    Graph(int v) : V(v), adj(v), color(v, WHITE), 
                   discovery(v, -1), finish(v, -1) {}
    
    void addEdge(int u, int v) { adj[u].push_back(v); }
    
    void dfsVisit(int u) {
        color[u] = GRAY;
        discovery[u] = ++time;
        
        for (int v : adj[u]) {
            if (color[v] == WHITE) {
                // Tree Edge
                dfsVisit(v);
            } else if (color[v] == GRAY) {
                // Back Edge (Cycle)
                cout << "Back Edge: " << u << " -> " << v << "\n";
            } else { // BLACK
                // Forward or Cross Edge
                if (discovery[u] < discovery[v]) {
                    cout << "Forward Edge: " << u << " -> " << v << "\n";
                    forwardEdges.emplace_back(u, v);
                } else {
                    cout << "Cross Edge: " << u << " -> " << v << "\n";
                }
            }
        }
        
        color[u] = BLACK;
        finish[u] = ++time;
    }
    
    void dfs() {
        time = 0;
        fill(color.begin(), color.end(), WHITE);
        forwardEdges.clear();
        
        for (int u = 0; u < V; u++) {
            if (color[u] == WHITE) dfsVisit(u);
        }
    }
    
    void printTimestamps() {
        cout << "\nVertex | Discovery | Finish\n";
        for (int i = 0; i < V; i++) {
            cout << "   " << i << "   |    " << discovery[i] 
                 << "     |   " << finish[i] << "\n";
        }
    }
};

int main() {
    // Example from article: 5 vertices
    Graph g(5);
    // Adjacency Matrix from article:
    // 0: 1, 3
    // 1: 3
    // 2: 4
    // 3: 1, 2
    // 4: 0, 1
    g.addEdge(0, 1);
    g.addEdge(0, 3);
    g.addEdge(1, 3);
    g.addEdge(2, 4);
    g.addEdge(3, 1);
    g.addEdge(3, 2);
    g.addEdge(4, 0);
    g.addEdge(4, 1);
    
    cout << "DFS Edge Classification:\n";
    g.dfs();
    g.printTimestamps();
    
    cout << "\nForward Edges Found:\n";
    for (auto [u, v] : g.forwardEdges) {
        cout << "  " << u << " -> " << v << "\n";
    }
    
    return 0;
}

ผลลัพธ์

DFS Edge Classification:
Tree Edge: 0 -> 1
Tree Edge: 1 -> 3
Tree Edge: 3 -> 2
Tree Edge: 2 -> 4
Back Edge: 3 -> 1
Forward Edge: 0 -> 3
Cross Edge: 4 -> 0
Cross Edge: 4 -> 1

Vertex | Discovery | Finish
   0   |    1     |   10
   1   |    2     |   9
   2   |    4     |   7
   3   |    3     |   8
   4   |    5     |   6

Forward Edges Found:
  0 -> 3

อธิบาย Forward Edge: 0 → 3

DFS Tree: 0→1→3→2→4

Edge 0→3: Vertex 3 เป็น Descendant ของ 0 ใน Tree (ผ่าน 1) แต่ไม่ใช่ Tree Edge → Forward Edge

Discovery[0]=1 < Discovery[3]=3 ✓

Complexity

• Time: O(V + E)
• Space: O(V) สำหรับ Color, Discovery, Finish, Recursion Stack

Applications

• Cycle Detection (Back Edges)
• Topological Sort (No Back Edges = DAG)
• Strongly Connected Components (Kosaraju/Tarjan)
• Program Analysis (Control Flow Graphs)
• Database Deadlock Detection

Note on Original Article Code

โค้ดต้นฉบับใช้ Stack-based Approach พร้อม Manual Node Management ซึ่งซับซ้อนและ Error-prone โค้ดข้างต้นใช้ Recursive DFS มาตรฐาน พร้อม Color + Timestamp Classification ที่ชัดเจนและน่าเชื่อถือกว่า

C++ Program: Threaded Binary Tree Implementation (Inorder Traversal Without Stack/Recursion)

C++ Program: Check if Topological Sorting is Possible (DAG Detection)