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

Topological Sorting เรียงลำดับ Vertex ของ Directed Graph ให้ Edge (u,v) ทุกอันมี u อยู่ก่อน v ได้ก็ต่อเมื่อ Graph เป็น DAG (Directed Acyclic Graph) → ไม่มี Cycle

Algorithm: Kahn's Algorithm (BFS-based)

1. คำนวณ In-degree ของทุก Vertex
2. Enqueue Vertex ที่ In-degree = 0 ทั้งหมด
3. Dequeue Vertex u → Add to Result → ลด In-degree ของ Neighbors
4. ถ้า Neighbor In-degree กลายเป็น 0 → Enqueue
5. ถ้า Result Size = V → No Cycle (Topological Order Valid)
6. ถ้า Result Size < V → มี Cycle (Topological Sort Impossible)

Algorithm: DFS-based (Recursive)

1. DFS ทุก Vertex, Track Color (WHITE/GRAY/BLACK)
2. ถ้าเจอ GRAY Neighbor → Back Edge → Cycle Detected
3. Post-order: Push Vertex to Stack หลัง Visit ครบ
4. Reverse Stack = Topological Order

โค้ด C++ (Both Methods)

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;

class Graph {
    int V;
    vector> adj;
    
public:
    Graph(int v) : V(v), adj(v) {}
    
    void addEdge(int u, int v) { adj[u].push_back(v); }
    
    // Kahn's Algorithm (BFS) - Returns {hasCycle, topoOrder}
    pair> kahnTopologicalSort() {
        vector indegree(V, 0);
        for (int u = 0; u < V; u++)
            for (int v : adj[u]) indegree[v]++;
        
        queue q;
        for (int i = 0; i < V; i++)
            if (indegree[i] == 0) q.push(i);
        
        vector topo;
        int visited = 0;
        
        while (!q.empty()) {
            int u = q.front(); q.pop();
            topo.push_back(u);
            visited++;
            
            for (int v : adj[u]) {
                if (--indegree[v] == 0) q.push(v);
            }
        }
        
        return {visited != V, topo}; // true = has cycle
    }
    
    // DFS-based Topological Sort
    pair> dfsTopologicalSort() {
        vector color(V, 0); // 0=WHITE, 1=GRAY, 2=BLACK
        vector topo;
        bool hasCycle = false;
        
        function dfs = [&](int u) {
            color[u] = 1; // GRAY
            for (int v : adj[u]) {
                if (color[v] == 0) dfs(v);
                else if (color[v] == 1) hasCycle = true; // Back Edge
            }
            color[u] = 2; // BLACK
            topo.push_back(u);
        };
        
        for (int i = 0; i < V; i++)
            if (color[i] == 0) dfs(i);
        
        reverse(topo.begin(), topo.end());
        return {hasCycle, topo};
    }
    
    void printGraph() {
        for (int u = 0; u < V; u++) {
            cout << u << " -> ";
            for (int v : adj[u]) cout << v << " ";
            cout << "\n";
        }
    }
};

int main() {
    // Example from article: 6 vertices
    Graph g(6);
    g.addEdge(5, 2);
    g.addEdge(5, 0);
    g.addEdge(4, 0);
    g.addEdge(4, 1);
    g.addEdge(2, 3);
    g.addEdge(3, 1);
    
    cout << "Graph:\n"; g.printGraph();
    
    // Kahn's
    auto [hasCycle1, topo1] = g.kahnTopologicalSort();
    cout << "\nKahn's Algorithm:\n";
    cout << "Has Cycle: " << (hasCycle1 ? "YES" : "NO") << "\n";
    if (!hasCycle1) {
        cout << "Topological Order: ";
        for (int v : topo1) cout << v << " ";
        cout << "\n";
    }
    
    // DFS
    auto [hasCycle2, topo2] = g.dfsTopologicalSort();
    cout << "\nDFS Algorithm:\n";
    cout << "Has Cycle: " << (hasCycle2 ? "YES" : "NO") << "\n";
    if (!hasCycle2) {
        cout << "Topological Order: ";
        for (int v : topo2) cout << v << " ";
        cout << "\n";
    }
    
    // Test with Cycle
    Graph g2(3);
    g2.addEdge(0, 1);
    g2.addEdge(1, 2);
    g2.addEdge(2, 0); // Cycle!
    
    auto [cycle, _] = g2.kahnTopologicalSort();
    cout << "\nGraph with Cycle (0->1->2->0):\n";
    cout << "Has Cycle: " << (cycle ? "YES" : "NO") << "\n";
    
    return 0;
}

ผลลัพธ์

Graph:
0 -> 
1 -> 
2 -> 3
3 -> 1
4 -> 0 1
5 -> 2 0

Kahn's Algorithm:
Has Cycle: NO
Topological Order: 5 4 2 3 1 0

DFS Algorithm:
Has Cycle: NO
Topological Order: 5 4 2 3 1 0

Graph with Cycle (0->1->2->0):
Has Cycle: YES

Comparison

Applications

• Task Scheduling (Dependencies)
• Course Prerequisites
• Build Systems (Make, CMake, Bazel)
• Package Managers (npm, pip, cargo)
• Spreadsheet Recalculation
• Instruction Scheduling (Compilers)

Handling Multiple Valid Orders

ใช้ priority_queue (Min-Heap) แทน Queue ใน Kahn's เพื่อให้ได้ Lexicographically Smallest Order

priority_queue, greater> pq;
// ... same logic, gives smallest available vertex first

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

C++ Program: Detect Cycle in Directed Graph using Topological Sort (Kahn's Algorithm)