Cycle Detection in the Directed Graph using the DFS

Cycle detection in a directed graph is a classic algorithm problem and must-know for backend and platform engineers.

What is a cycle in a directed graph?

• The edges of a directed graph, which resemble arrows pointing from one node to another, have a specified direction.

• When you can begin at a node, follow the directed edges, and ultimately return to the same node without retracing any edges backward, you have a cycle.

In simple terms: A cycle is a loop of dependencies.
Imagine tasks A, B, and C with these relationships:
A → B (A must be done before B)
B → C (B must be done before C)
C → A (C must be done before A)
Here, you’re stuck in a loop:
A depends on B → B depends on C → C depends on A.
There’s no valid starting point — that’s a cycle

Why cycle detection is important?

• Cycles mean circular dependencies → no valid ordering is possible
• When you can continue following arrows and go back to the beginning point, you have a cycle in a directed graph. Tasks or dependencies cannot be arranged in a valid sequence because of this loop.

Why DFS for Cycle Detection?

• Because it thoroughly examines each path before turning around, Depth-First Search (DFS) is especially well-suited for identifying cycles in a directed graph and aids in the effective detection of loops.
• Because it tracks the current traversal, follows the paths naturally, and effectively detects cycles in directed graphs, DFS is recommended.

Intuition for DFS-based Cycle Detection

Step 1: Select any node that hasn't been investigated yet and launch DFS from it.

• This guarantees that every disconnected graph element is examined.

Step 2: Add it to the recursion stack and mark it as visited.

• Nodes that we've seen at least once are indicated by Visited[].

• Nodes that are a component of the current DFS path are marked by the Recursion Stack (PathVisited[]).

• Why are there two arrays?

Visited[] stops unnecessary node revisits.
Cycles along the present path are detected with the use of the recursion stack.

Step 3: Recursively examine every neighbor

• Visit each of the current node's neighbors.
• For every neighbor:
  • Call DFS about it if it hasn't been visited.
  • A cycle is identified if it is in the recursion stack (we're revisiting a node in the current path).
  • Repeat for everyone.

Step 4: Identifying the Cycle - We may identify a loop as soon as we discover a neighbor that is already on the recursion stack.

• An illustration of intuition
  • Imagine traversing a maze.
  • You are going around in circles if you enter a room that you have already visited on this journey.

Step 5: Backtracking - Take the node out of the recursion stack after exploring all of its neighbors.

• This stage guarantees that the recursion stack only includes nodes that are presently being explored and not ones that have been fully processed.

Step 6: Do this for every node that hasn't been visited.

• Start DFS on the unconnected components that haven't been visited yet.This guarantees full cycle detection throughout the graph.

Important Point to Keep in Mind

• The key to identifying cycles is the recursion stack.
• Visited[] by itself is insufficient.
• You can only determine whether a cycle is present by monitoring the nodes in the current DFS path.
• Consider this: "I'm in a loop if I go back to a node that's still on my current path!"

Let's understand through the Dry Run,

Let’s take 4 nodes (0, 1, 2, 3) with edges:
0 → 1
1 → 2
2 → 3
3 → 1 (Back edge → creates cycle)

Initial State

1.Start DFS at Node 0
Mark 0 visited & in recursion stack.

Neighbors of 0: 1

2: DFS(1)
Mark 1 visited & in recursion stack.

Neighbors of 1: 2

3: DFS(2)
Mark 2 visited & in recursion stack.

Neighbors of 2: 3

4: DFS(3)
Mark 3 visited & in recursion stack.

Neighbors of 3: 1

But 1 is already in recursion stack → Cycle Detected!

Why this detects a cycle:

When a DFS from node u sees an edge u → v where v is already on the current recursion stack, it means there is a path from v down to u (because v is an ancestor in the recursion), and now u points back to v — so we have a directed cycle.

Backtracking (after detection)

After detecting the cycle, typical DFS cycle-detection code will return True up the call chain to stop further exploration (or record the cycle).
Recursion unwinds, and recStack entries are cleared (set back to False) as each call returns.

C++ Code: Cycle Detection in Directed Graph (DFS)

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

bool dfsCycle(int node, vector<vector<int>> &graph, vector<bool> &visited, vector<bool> &recStack) {
    visited[node] = true;
    recStack[node] = true;

    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            if (dfsCycle(neighbor, graph, visited, recStack))
                return true;
        }
        else if (recStack[neighbor]) {
            // Found a back edge → cycle
            return true;
        }
    }

    recStack[node] = false; // backtrack
    return false;
}

bool isCyclic(int V, vector<pair<int,int>> &edges) {
    vector<vector<int>> graph(V);
    for (auto &e : edges) {
        graph[e.first].push_back(e.second);
    }

    vector<bool> visited(V, false);
    vector<bool> recStack(V, false);

    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            if (dfsCycle(i, graph, visited, recStack))
                return true;
        }
    }
    return false;
}

int main() {
    int V = 4;
    vector<pair<int,int>> edges = {
        {0, 1},
        {1, 2},
        {2, 3},
        {3, 1} // cycle here
    };

    if (isCyclic(V, edges))
        cout << "Cycle detected in the graph!" << endl;
    else
        cout << "No cycle found." << endl;

    return 0;
}

Time Complexity
We perform a DFS traversal of the graph.
In DFS, each vertex (V) is visited once, and each edge (E) is explored once.
Thus, total complexity: O(V+E)

Space Complexity
Visited Array → O(V)
Recursion Stack Array → O(V)
Recursive Call Stack (function calls) → O(V) in the worst case (when the graph is like a long chain).
So, total space complexity: O(V)