Detect Cycle in a Directed Graph

Given a directed graph, check if it contains at least one cycle. A directed cycle is a sequence of directed edges where a vertex is reachable from itself.

Why the Undirected Logic Fails

In a directed graph, simply checking if an already-visited neighbor is not the parent leads to false positives.

Consider this Directed Acyclic Graph (DAG):

If we start DFS from 0:

1. Visit 0 $\rightarrow$ Visit 1.
2. Backtrack to 0 $\rightarrow$ Visit 2.
3. From 2, we look at its neighbor 1. 1 is already visited, and the parent of 2 is 0 (not 1).
4. If we used the undirected logic, we would incorrectly flag this as a cycle. However, this is not a cycle; it is just two paths converging on 1 (a cross-edge).

The Logic (DFS with Recursion Stack Tracker)

To detect a cycle, we must check for back-edges—edges that point back to an ancestor in the active DFS path. We do this by keeping track of the vertices currently active in the recursion stack (recStack).

1. Maintain a visited set to avoid repeating work.
2. Maintain a recStack set to track nodes in the current DFS path.
3. For each vertex:
   • If the vertex is already in recStack, we have looped back $\rightarrow$ Cycle detected.
   • If the vertex is already in visited (but not recStack), skip it (it's already been fully explored and is cycle-free).
4. Recursively visit all neighbors.
5. After exploring all paths from the current node, remove it from recStack (backtrack).

Visual Example

Let's look at this cyclic directed graph:

1. Start DFS at 0.
   • visited = {0}
   • recStack = {0}
2. Visit neighbor 1 of 0.
   • visited = {0, 1}
   • recStack = {0, 1}
3. Visit neighbor 2 of 1.
   • visited = {0, 1, 2}
   • recStack = {0, 1, 2}
4. Neighbor of 2 is 0. 0 is already in recStack!
5. Cycle detected!

JavaScript Code Implementation

class Graph {
    constructor() {
        this.list = {};
    }
 
    addVertex(vertex) {
        if (!this.list[vertex]) this.list[vertex] = [];
    }
 
    addEdge(v1, v2) {
        this.addVertex(v1);
        this.addVertex(v2);
        this.list[v1].push(v2); // Directed edge v1 -> v2
    }
 
    // Main check
    isCyclic() {
        const visited = {};
        const recStack = {};
 
        // Initialize trackers
        Object.keys(this.list).forEach(vertex => {
            visited[vertex] = false;
            recStack[vertex] = false;
        });
 
        // Run DFS helper for all unvisited nodes
        for (let vertex of Object.keys(this.list)) {
            if (!visited[vertex]) {
                if (this._isCyclicUtil(vertex, visited, recStack)) {
                    return true;
                }
            }
        }
        return false;
    }
 
    // DFS Utility
    _isCyclicUtil(v, visited, recStack) {
        // If node is already in recursion stack, we found a loop
        if (recStack[v]) return true;
 
        // If node is already fully explored, no need to check again
        if (visited[v]) return false;
 
        // Add node to visited and active recursion path
        visited[v] = true;
        recStack[v] = true;
 
        const neighbors = this.list[v] || [];
        for (let neighbor of neighbors) {
            if (this._isCyclicUtil(neighbor, visited, recStack)) {
                return true;
            }
        }
 
        // Backtrack: Remove node from active path stack
        recStack[v] = false;
        return false;
    }
}
 
// Driver code
const g = new Graph();
g.addEdge("0", "1");
g.addEdge("0", "2");
g.addEdge("1", "2");
g.addEdge("2", "0");
g.addEdge("3", "3");
 
console.log("Directed Graph contains cycle:", g.isCyclic()); // Output: true

Complexity Analysis

• Time Complexity: $O(V + E)$
  • Standard DFS traversal covering all reachable vertices and edges.
• Space Complexity: $O(V)$
  • Recursive call stack and tracking structures.