Cycle Detection in Directed Graph in DSA Java

Mental Model

We want to find if there is a path that starts and ends at the same node following the direction of edges.

Analogy: Imagine a one-way street map where you want to check if you can start driving from a place and eventually come back to it by following the one-way roads.

0 -> 1 -> 2
↑         ↓
└─────────3

Dry Run Walkthrough

Input: Graph with edges: 0->1, 1->2, 2->3, 3->0

Goal: Detect if there is a cycle in the directed graph

Step 1: Start DFS from node 0, mark 0 as visiting

Visiting: [0], Visited: []

Why: We begin exploring from node 0 to find cycles

Step 2: Move to node 1 from 0, mark 1 as visiting

Visiting: [0, 1], Visited: []

Why: Follow edge 0->1 to continue DFS

Step 3: Move to node 2 from 1, mark 2 as visiting

Visiting: [0, 1, 2], Visited: []

Why: Follow edge 1->2 to continue DFS

Step 4: Move to node 3 from 2, mark 3 as visiting

Visiting: [0, 1, 2, 3], Visited: []

Why: Follow edge 2->3 to continue DFS

Step 5: From node 3, find edge back to 0 which is already visiting

Visiting: [0, 1, 2, 3], Visited: []

Why: Finding a node in visiting state means a cycle exists

Result:

Cycle detected because node 0 is revisited while still in visiting state

Annotated Code

DSA Java

import java.util.*;

public class CycleDetectionDirectedGraph {
    private final int V;
    private final List<List<Integer>> adj;

    public CycleDetectionDirectedGraph(int vertices) {
        this.V = vertices;
        adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
    }

    public void addEdge(int src, int dest) {
        adj.get(src).add(dest);
    }

    private boolean dfs(int node, boolean[] visited, boolean[] recStack) {
        visited[node] = true;
        recStack[node] = true; // mark node as visiting

        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                if (dfs(neighbor, visited, recStack)) {
                    return true; // cycle found in deeper call
                }
            } else if (recStack[neighbor]) {
                return true; // cycle found due to back edge
            }
        }

        recStack[node] = false; // mark node as done visiting
        return false;
    }

    public boolean hasCycle() {
        boolean[] visited = new boolean[V];
        boolean[] recStack = new boolean[V];

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

    public static void main(String[] args) {
        CycleDetectionDirectedGraph graph = new CycleDetectionDirectedGraph(4);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);
        graph.addEdge(3, 0);

        System.out.println(graph.hasCycle() ? "Cycle detected" : "No cycle detected");
    }
}

visited[node] = true; recStack[node] = true; // mark node as visiting

mark current node as visited and currently in recursion stack

for (int neighbor : adj.get(node)) {

iterate over all neighbors of current node

if (!visited[neighbor]) { if (dfs(neighbor, visited, recStack)) { return true; // cycle found in deeper call } }

if neighbor not visited, recursively visit it and check for cycle

else if (recStack[neighbor]) { return true; // cycle found due to back edge }

if neighbor is in recursion stack, cycle detected

recStack[node] = false; // mark node as done visiting

remove node from recursion stack after exploring all neighbors

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

start DFS from each unvisited node to cover disconnected graph parts

Output

Cycle detected

Complexity Analysis

Time: O(V + E) because each vertex and edge is visited once during DFS

Space: O(V) for recursion stack and visited arrays

vs Alternative: Compared to using topological sort which also detects cycles, DFS is simpler and direct for cycle detection

Edge Cases

Empty graph with no vertices

No cycle detected because there are no nodes

DSA Java

for (int i = 0; i < V; i++) { if (!visited[i]) {

Graph with single node and no edges

No cycle detected because no edges to form cycle

DSA Java

for (int i = 0; i < V; i++) { if (!visited[i]) {

Graph with multiple disconnected components, one with cycle

Cycle detected because DFS finds cycle in one component

DSA Java

if (dfs(i, visited, recStack)) { return true; }

When to Use This Pattern

When you see a problem asking if a directed graph has a loop or cycle, use DFS with recursion stack tracking to detect back edges indicating cycles.

Common Mistakes

Mistake: Not using a recursion stack to track nodes currently being explored, leading to false negatives.
Fix: Use a separate recursion stack array to mark nodes in the current DFS path to detect back edges.

Mistake: Marking nodes as visited only after all neighbors are processed, causing infinite recursion.
Fix: Mark nodes as visited and in recursion stack immediately when starting DFS on them.

Summary

Detects if a directed graph contains a cycle by DFS and recursion stack tracking.

Use when you need to find loops in directed graphs, such as dependency checks or scheduling.

The key insight is that revisiting a node currently in the recursion stack means a cycle exists.

Practice

1. What does cycle detection in a directed graph help us find?

easy

A. The maximum degree of any node

B. The shortest path between two nodes

C. The total number of nodes in the graph

D. Whether there is a path that starts and ends at the same node following the direction of edges

Solution

1. Step 1: Understand cycle in directed graph

   A cycle means a path that starts and ends at the same node following edge directions.

2. Step 2: Identify what cycle detection finds

   Cycle detection checks if such a path exists in the graph.

3. Final Answer:

   Whether there is a path that starts and ends at the same node following the direction of edges -> Option D

4. Quick Check:

   Cycle detection = finding directed cycles [OK]

Hint: Cycle means path loops back following edge directions [OK]

Common Mistakes:

• Confusing cycle with shortest path
• Ignoring edge directions
• Thinking cycle means any repeated node without direction

2. Which Java data structure is commonly used to keep track of nodes currently in the recursion stack during DFS for cycle detection?

easy

A. Stack

B. HashSet

C. Queue

D. ArrayList

Solution

1. Step 1: Identify recursion stack tracking

   During DFS, nodes in the current path are tracked to detect back edges indicating cycles.

2. Step 2: Choose suitable data structure

   A HashSet is used to quickly check if a node is in the current recursion stack.

3. Final Answer:

   HashSet -> Option B

4. Quick Check:

   Use HashSet to track recursion stack nodes [OK]

Hint: Use HashSet for O(1) check if node is in recursion stack [OK]

Common Mistakes:

• Using Queue which is FIFO, not suitable here
• Using Stack but not checking membership efficiently
• Using ArrayList which is slower for membership check

3. What will be the output of the following Java code snippet detecting cycle in a directed graph?

import java.util.*;

public class GraphCycle {
    private final int V = 3;
    private final List adj = new ArrayList<>();
    private final boolean[] visited = new boolean[V];
    private final boolean[] recStack = new boolean[V];

    public GraphCycle() {
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        adj.get(0).add(1);
        adj.get(1).add(2);
        adj.get(2).add(0);
    }

    private boolean dfs(int node) {
        if (recStack[node]) return true;
        if (visited[node]) return false;
        visited[node] = true;
        recStack[node] = true;
        for (int neighbor : adj.get(node)) {
            if (dfs(neighbor)) return true;
        }
        recStack[node] = false;
        return false;
    }

    public boolean hasCycle() {
        for (int i = 0; i < V; i++) {
            if (dfs(i)) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        GraphCycle graph = new GraphCycle();
        System.out.println(graph.hasCycle());
    }
}

medium

A. true

B. false

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Analyze graph edges

   Edges: 0->1, 1->2, 2->0 form a cycle (0->1->2->0).

2. Step 2: Trace DFS cycle detection

   DFS from node 0 visits 1, then 2, then back to 0 which is in recursion stack, so returns true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Cycle exists in graph = true [OK]

Hint: Cycle if DFS revisits node in recursion stack [OK]

Common Mistakes:

• Ignoring recursion stack check
• Assuming no cycle because visited[] is true
• Confusing visited[] and recStack[] roles

4. Identify the bug in this cycle detection code snippet for a directed graph:

boolean dfs(int node, boolean[] visited, boolean[] recStack, List adj) {
    visited[node] = true;
    recStack[node] = true;
    for (int neighbor : adj.get(node)) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited, recStack, adj);
        } else if (recStack[neighbor]) {
            return true;
        }
    }
    recStack[node] = false;
    return false;
}

medium

A. Loop iterates over wrong adjacency list

B. recStack is not reset to false

C. Missing return statement in recursive call

D. visited array is not updated

Solution

1. Step 1: Check recursive call handling

   Recursive call dfs(neighbor, ...) is made but its return value is ignored.

2. Step 2: Understand impact on cycle detection

   If dfs(neighbor) returns true (cycle found), this should be returned immediately to propagate detection.

3. Final Answer:

   Missing return statement in recursive call -> Option C

4. Quick Check:

   Return recursive call result to detect cycles [OK]

Hint: Return recursive dfs result to catch cycles early [OK]

Common Mistakes:

• Ignoring return value of recursive dfs
• Not resetting recStack[node] to false
• Confusing visited and recStack roles

5. Given a directed graph represented as adjacency list:

{
  0: [1],
  1: [2],
  2: [3],
  3: [1, 4],
  4: []
}

Which nodes are part of at least one cycle?

hard

A. [1, 2, 3]

B. [0, 1, 2, 3]

C. [1, 3]

D. [0, 4]

Solution

1. Step 1: Identify cycles in graph

   Edges: 1->2, 2->3, 3->1 form a cycle involving nodes 1, 2, 3.

2. Step 2: Check other nodes

   Node 0 points to 1 but is not in cycle; node 4 has no outgoing edges.

3. Final Answer:

   [1, 2, 3] -> Option A

4. Quick Check:

   Cycle nodes = [1, 2, 3] [OK]

Hint: Cycle nodes form closed loop edges [OK]

Common Mistakes:

• Including nodes that only lead to cycle but not in it
• Missing nodes inside the cycle
• Confusing cycle presence with reachability