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

การตรวจสอบ Cycle ใน Directed Graph สามารถทำได้โดยพยายามทำ Topological Sort ถ้าทำไม่ได้ (Result Size < V) แสดงว่ามี Cycle

หลักการ: Kahn's Algorithm for Cycle Detection

1. คำนวณ In-degree ทุก Vertex
2. Queue เก็บ Vertex ที่ In-degree = 0
3. Process Queue: Pop u, ลด In-degree ของ Neighbors
4. นับจำนวน Vertex ที่ Process ได้ (count)
5. ถ้า count == V → No Cycle (DAG)
6. ถ้า count < V → Has Cycle (Vertex ที่เหลืออยู่ใน Cycle)

Why It Works

ใน DAG ต้องมี Vertex อย่างน้อย 1 ตัวที่ In-degree = 0 (Source) หาก Process ไปเรื่อยๆ จะหมดทุก Vertex แต่ถ้ามี Cycle Vertex ใน Cycle จะมี In-degree ≥ 1 ตลอดกาล → ไม่ออกจาก Queue

โค้ด C++ (Focus on Cycle Detection)

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

class DirectedGraph {
    int V;
    vector> adj;
    
public:
    DirectedGraph(int v) : V(v), adj(v) {}
    
    void addEdge(int u, int v) { adj[u].push_back(v); }
    
    // Returns true if cycle exists
    bool hasCycleKahn() {
        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);
        
        int count = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            count++;
            for (int v : adj[u]) {
                if (--indegree[v] == 0) q.push(v);
            }
        }
        
        return count != V; // Cycle exists if not all vertices processed
    }
    
    // DFS-based Cycle Detection (Alternative)
    bool hasCycleDFS() {
        vector color(V, 0); // 0=WHITE, 1=GRAY, 2=BLACK
        
        function dfs = [&](int u) {
            color[u] = 1; // GRAY
            for (int v : adj[u]) {
                if (color[v] == 0) {
                    if (dfs(v)) return true;
                } else if (color[v] == 1) {
                    return true; // Back Edge Found
                }
            }
            color[u] = 2; // BLACK
            return false;
        };
        
        for (int i = 0; i < V; i++)
            if (color[i] == 0 && dfs(i)) return true;
        
        return false;
    }
    
    // Find Cycle Path (DFS with Parent Tracking)
    vector findCycle() {
        vector color(V, 0), parent(V, -1);
        int cycleStart = -1, cycleEnd = -1;
        
        function dfs = [&](int u) {
            color[u] = 1;
            for (int v : adj[u]) {
                if (color[v] == 0) {
                    parent[v] = u;
                    if (dfs(v)) return true;
                } else if (color[v] == 1) {
                    cycleEnd = u;
                    cycleStart = v;
                    return true;
                }
            }
            color[u] = 2;
            return false;
        };
        
        for (int i = 0; i < V; i++)
            if (color[i] == 0 && dfs(i)) break;
        
        if (cycleStart == -1) return {};
        
        // Reconstruct Cycle
        vector cycle;
        cycle.push_back(cycleStart);
        for (int v = cycleEnd; v != cycleStart; v = parent[v])
            cycle.push_back(v);
        cycle.push_back(cycleStart);
        reverse(cycle.begin(), cycle.end());
        return cycle;
    }
};

int main() {
    // Example 1: Graph with Cycle (0→1→2→3→4→0)
    DirectedGraph g1(5);
    g1.addEdge(0, 1);
    g1.addEdge(1, 2);
    g1.addEdge(2, 3);
    g1.addEdge(3, 4);
    g1.addEdge(4, 0); // Cycle!
    
    cout << "Graph 1 (5-cycle):\n";
    cout << "Kahn's: " << (g1.hasCycleKahn() ? "HAS CYCLE" : "NO CYCLE") << "\n";
    cout << "DFS:    " << (g1.hasCycleDFS() ? "HAS CYCLE" : "NO CYCLE") << "\n";
    auto cycle = g1.findCycle();
    if (!cycle.empty()) {
        cout << "Cycle Path: ";
        for (size_t i = 0; i < cycle.size(); i++) {
            cout << cycle[i] << (i+1 < cycle.size() ? " -> " : "");
        }
        cout << "\n";
    }
    
    // Example 2: DAG (from previous article)
    DirectedGraph g2(6);
    g2.addEdge(5, 2);
    g2.addEdge(5, 0);
    g2.addEdge(4, 0);
    g2.addEdge(4, 1);
    g2.addEdge(2, 3);
    g2.addEdge(3, 1);
    
    cout << "\nGraph 2 (DAG):\n";
    cout << "Kahn's: " << (g2.hasCycleKahn() ? "HAS CYCLE" : "NO CYCLE") << "\n";
    cout << "DFS:    " << (g2.hasCycleDFS() ? "HAS CYCLE" : "NO CYCLE") << "\n";
    
    // Example 3: Disconnected Graph with Cycle in One Component
    DirectedGraph g3(6);
    g3.addEdge(0, 1);
    g3.addEdge(1, 2);
    g3.addEdge(2, 0); // Cycle in 0-1-2
    g3.addEdge(3, 4);
    g3.addEdge(4, 5); // No cycle in 3-4-5
    
    cout << "\nGraph 3 (Disconnected, Cycle in Component 1):\n";
    cout << "Kahn's: " << (g3.hasCycleKahn() ? "HAS CYCLE" : "NO CYCLE") << "\n";
    cycle = g3.findCycle();
    if (!cycle.empty()) {
        cout << "Cycle Path: ";
        for (size_t i = 0; i < cycle.size(); i++) {
            cout << cycle[i] << (i+1 < cycle.size() ? " -> " : "");
        }
        cout << "\n";
    }
    
    return 0;
}

ผลลัพธ์

Graph 1 (5-cycle):
Kahn's: HAS CYCLE
DFS:    HAS CYCLE
Cycle Path: 0 -> 1 -> 2 -> 3 -> 4 -> 0

Graph 2 (DAG):
Kahn's: NO CYCLE
DFS:    NO CYCLE

Graph 3 (Disconnected, Cycle in Component 1):
Kahn's: HAS CYCLE
Cycle Path: 0 -> 1 -> 2 -> 0

Complexity

Directed vs Undirected Cycle Detection

• Directed: Kahn's / DFS with Colors (Back Edge = Cycle)
• Undirected: DFS/Union-Find, Ignore Parent Edge (u→v where v is parent of u)

Applications

• Deadlock Detection (Resource Allocation Graph)
• Circular Dependency Check (Build Systems, Package Managers)
• Circuit Design (Feedback Loops)
• Database Serializability (Precedence Graph)
• Spreadsheet Circular References

Limitations of Kahn's for Cycle Info

Kahn's Algorithm บอกได้ว่า "มี Cycle" แต่ไม่บอกว่า Cycle อยู่ที่ไหนหรือเป็นรูปแบบไหน ต้องใช้ DFS + Parent Tracking เพื่อหา Path จริง

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

C++ Program: Check if Graph Construction is Possible from Degree Sequence (Graphic Sequence)