Graphs

Graph Patterns: Cycle Detection in Directed Graphs

May 2026

7 min read

Detecting a cycle in an undirected graph is easy: if you see a visited node, it's a cycle. But in Directed Graphs, distinct paths can merge without forming loops. We must track the active recursion stack.

Introduction

In a directed graph, multiple distinct paths can lead to the same destination without ever forming a loop. If we only use a standard visited array, our algorithm will trigger false positives when these paths merge.

The Path Tracker

The secret is maintaining two separate boolean arrays:

vis: Tracks nodes we have completely processed to avoid redundant work.
pathVis: Tracks nodes that are currently active in our exact present recursion stack.

When we traverse down a path, we mark both arrays as true. If we hit a dead end and need to backtrack, we leave vis as true, but we revert pathVis to false because we are stepping out of that path.

If we ever encounter a neighbor that is marked true in both vis AND pathVis, we have crashed back into our own active tail. We have found a confirmed cycle.

Implementation

java

class Solution {
    public boolean isCyclic(int V, ArrayList<ArrayList<Integer>> adj) {
        boolean[] vis = new boolean[V];
        boolean[] pathVis = new boolean[V];
        
        for (int i = 0; i < V; i++) {
            if (!vis[i]) {
                if (dfsCheck(i, adj, vis, pathVis)) return true;
            }
        }
        return false;
    }
    
    private boolean dfsCheck(int node, ArrayList<ArrayList<Integer>> adj, boolean[] vis, boolean[] pathVis) {
        vis[node] = true;
        pathVis[node] = true; // Mark node as part of current active path
        
        for (int neighbor : adj.get(node)) {
            if (!vis[neighbor]) {
                if (dfsCheck(neighbor, adj, vis, pathVis)) return true;
            } 
            else if (pathVis[neighbor]) {
                // Node is visited AND currently in the active path
                return true; 
            }
        }
        
        // Backtrack: Remove node from active path as we retreat
        pathVis[node] = false; 
        return false;
    }
}