G-19: Detect Cycle in a Directed Graph Using DFS

Detecting a cycle in a directed graph is a foundational algorithmic problem in graph theory. While Depth First Search (DFS) can easily detect cycles in undirected graphs by checking if an adjacent node has already been visited (excluding the direct parent), that exact strategy completely fails when edges have a specific direction. This chapter explores why the naive approach fails, introduces the Path Visited array mental model, and breaks down the complete implementation in both Java and C++.

1. Why Undirected Cycle Detection Fails in Directed Graphs

In an undirected graph, an edge goes both ways. If you traverse from node A to node B, and from B you encounter an already visited node that is not your direct parent, it proves there is an alternate path back to A, confirming a cycle.

However, in a directed graph, edges are one-way streets.

Real-Life Analogy: One-Way Road Networks

Imagine navigating a city with strictly one-way streets. You drive down Street A to reach Street B, explore a neighborhood, hit a dead end, and drive back to the main square. Later, you take a completely different exit out of the main square down Street C, which eventually leads you to cross an intersection you already visited earlier via Street A.

• In an undirected map, that intersection crossing would mean you drove in a circle.
• In a one-way city, you never turned around; you simply took two different branches diverging from a common starting point that happened to cross paths later.

Because of this, standard single-visited tracking incorrectly flags valid branching paths as cycles in directed graphs.

2. The Core Mental Model: Visited vs. Path Visited Arrays

To accurately detect whether a cycle exists in a directed graph, we must guarantee that a node is revisited on the exact same traversal path, rather than on a separate, independent branch.

To achieve this, we maintain two separate arrays:

1. vis (Visited Array): Keeps a permanent record of all nodes that have been explored across any DFS traversal. This prevents redundant processing of components we have already fully evaluated.
2. pathVis (Path Visited Array): Tracks nodes that are currently active in the current recursion stack (current DFS path). When our DFS call finishes exploring a branch and backtracks, we unmark (0) the node in pathVis, but we keep it marked in vis.

Step-by-Step Path Lifecycle

3. Step-by-Step Execution Walkthrough

Let us trace a graph containing two separate components:

• Component 1 (Acyclic Branching): Nodes 1 -> 2 -> 3, where 3 branches to 4 -> 5 -> 6 and also to 7 -> 5.
• Component 2 (Cyclic Loop): Nodes 8 -> 9 -> 10 -> 8.

Execution Trace Table

4. Complete Flow Walkthrough (Text Diagram)

5. Implementation Code (Java & C++)

Java Implementation

import java.util.ArrayList;
import java.util.List;

public class Solution {
    
    private boolean dfsCheck(int node, List<List<Integer>> adj, int[] vis, int[] pathVis) {
        vis[node] = 1;
        pathVis[node] = 1;

        // Traverse all adjacent nodes
        for (Integer it : adj.get(node)) {
            // When the node is not visited
            if (vis[it] == 0) {
                if (dfsCheck(it, adj, vis, pathVis) == true) {
                    return true;
                }
            } 
            // If the node has been previously visited, 
            // but it has to be visited on the same traversal path
            else if (pathVis[it] == 1) {
                return true;
            }
        }

        // Backtracking step: remove from current path before returning
        pathVis[node] = 0;
        return false;
    }

    public boolean isCyclic(int V, List<List<Integer>> adj) {
        int[] vis = new int[V];
        int[] pathVis = new int[V];

        // Handle disconnected components
        for (int i = 0; i < V; i++) {
            if (vis[i] == 0) {
                if (dfsCheck(i, adj, vis, pathVis) == true) {
                    return true;
                }
            }
        }
        return false;
    }
}

C++ Implementation

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

class Solution {
private:
    bool dfsCheck(int node, vector<vector<int>>& adj, int vis[], int pathVis[]) {
        vis[node] = 1;
        pathVis[node] = 1;

        // Traverse for adjacent nodes
        for (auto it : adj[node]) {
            // When the node is not visited
            if (!vis[it]) {
                if (dfsCheck(it, adj, vis, pathVis))
                    return true;
            }
            // If the node has been previously visited
            // but it must be on the same path
            else if (pathVis[it]) {
                return true;
            }
        }

        // Backtracking: unmark path visited before returning
        pathVis[node] = 0;
        return false;
    }

public:
    bool isCyclic(int V, vector<vector<int>> adj[]) {
        int vis[V] = {0};
        int pathVis[V] = {0};

        for (int i = 0; i < V; i++) {
            if (!vis[i]) {
                if (dfsCheck(i, adj, vis, pathVis)) return true;
            }
        }
        return false;
    }
};

6. Complexity Analysis

Homework Challenge: Can you optimize the space complexity to use a single visited array instead of two separate arrays? Hint: Use different integer states (e.g., mark general visited as 1, and active path visited as 2). Share your solution in the community comments!

7. Summary and Key Takeaways

• Directed vs. Undirected Difference: Standard undirected cycle detection algorithms fail on directed graphs because intersecting independent branches are incorrectly flagged as cycles.
• The Path Visited Principle: A cycle in a directed graph exists if and only if a node is encountered that is already active in the current recursion path.
• Two-Array Strategy: Maintain a global vis array to prevent redundant work across components, and a local pathVis array to track the active DFS stack.
• Backtracking Resets: Always reset pathVis[node] = 0 when backtracking out of a node, while leaving vis[node] = 1 intact.
• Disconnected Components: Always loop through all nodes from 0 to V-1 to ensure graph components without incoming edges from node 0 are fully evaluated.
• Early Return Optimization: The moment any recursive DFS call detects pathVis[it] == 1, bubble the true result immediately up the call stack without checking remaining neighbors.