Cycle Detection in Directed Graph in DSA Java - Execution Trace

Concept Flow - Cycle Detection in Directed Graph

Start at each unvisited node

↓

Mark node as visited and in recursion stack

↓

For each neighbor

↓

If neighbor not visited

→Recurse on neighbor

↓

If cycle found, return true

↓

If neighbor in recursion stack

→Cycle detected, return true

↓

Remove node from recursion stack

↓

No cycle found from this node, continue

↓

All nodes processed, no cycle found

↓

Return false

The algorithm visits each node, marks it in a recursion stack, explores neighbors recursively, and detects a cycle if a neighbor is already in the recursion stack.

Execution Sample

DSA Java

boolean dfs(int node) {
  visited[node] = true;
  recStack[node] = true;
  for (int neighbor : graph[node]) {
    if (!visited[neighbor] && dfs(neighbor)) return true;
    else if (recStack[neighbor]) return true;
  }
  recStack[node] = false;
  return false;
}

This code checks if a cycle exists starting from a given node using DFS and recursion stack.

Execution Table

Step	Operation	Current Node	Visited Set	Recursion Stack	Action	Graph State
1	Start DFS at node 0	0	[0]	[0]	Mark node 0 visited and in recursion stack	0 -> 1, 0 -> 2
2	Explore neighbor 1 of node 0	1	[0,1]	[0,1]	Mark node 1 visited and in recursion stack	0 -> 1, 0 -> 2, 1 -> 2
3	Explore neighbor 2 of node 1	2	[0,1,2]	[0,1,2]	Mark node 2 visited and in recursion stack	0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0
4	Explore neighbor 0 of node 2	0	[0,1,2]	[0,1,2]	Node 0 is in recursion stack -> cycle detected	Cycle found
5	Return true up recursion	2	[0,1,2]	[0,1,2]	Cycle detected, return true	Cycle found
6	Return true up recursion	1	[0,1,2]	[0,1,2]	Cycle detected, return true	Cycle found
7	Return true up recursion	0	[0,1,2]	[0,1,2]	Cycle detected, return true	Cycle found
8	DFS ends with cycle detected	-	[0,1,2]	[0,1,2]	Cycle detected in graph	Cycle found

💡 Cycle detected when node 0 is found in recursion stack during exploration from node 2

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 8
visited	[false,false,false]	[true,false,false]	[true,true,false]	[true,true,true]	[true,true,true]	[true,true,true]
recStack	[false,false,false]	[true,false,false]	[true,true,false]	[true,true,true]	[true,true,true]	[true,true,true]
currentNode	null	0	1	2	0	null

Key Moments - 3 Insights

Why do we check if a neighbor is in the recursion stack instead of just visited?

Because a node being visited means it was processed at some point, but being in the recursion stack means it is still in the current path. Finding a neighbor in the recursion stack (see Step 4 in execution_table) means a cycle exists.

What happens if the graph has no edges?

The DFS will mark each node visited and remove it from recursion stack immediately without finding any neighbors, so no cycle is detected. This is shown by the absence of recursion stack conflicts in the execution_table.

Why do we remove the node from recursion stack after exploring all neighbors?

Removing the node means we finished exploring all paths from it. This prevents false cycle detection when backtracking to other branches.

Visual Quiz - 3 Questions

Look at the execution_table, what is the recursion stack after Step 2?

A [true,false,false]

B [false,false,false]

C [true,true,false]

D [true,true,true]

💡 Hint

Check the 'Recursion Stack' column at Step 2 in execution_table

At which step does the algorithm detect a cycle?

A Step 3

B Step 4

C Step 5

D Step 8

💡 Hint

Look for 'cycle detected' in the 'Action' column in execution_table

If the graph had no edges, how would the recursion stack change during DFS?

A It would never have more than one node at a time

B It would grow indefinitely

C It would be empty from the start

D It would contain all nodes at once

💡 Hint

Think about recursion stack usage when no neighbors exist to recurse on

Concept Snapshot

Cycle Detection in Directed Graph using DFS:
- Visit each node, mark visited and add to recursion stack
- For each neighbor:
  - If not visited, recurse
  - If in recursion stack, cycle found
- Remove node from recursion stack after exploring neighbors
- If any recursion finds cycle, graph has cycle
- Otherwise, no cycle

Full Transcript

Cycle detection in a directed graph uses depth-first search (DFS) with a recursion stack to track nodes in the current path. Starting from each unvisited node, we mark it visited and add it to the recursion stack. We then explore each neighbor. If a neighbor is not visited, we recurse on it. If a neighbor is already in the recursion stack, it means a cycle exists. After exploring all neighbors, we remove the node from the recursion stack. If no cycles are found after processing all nodes, the graph is acyclic. The execution table shows a graph with nodes 0, 1, 2 and edges forming a cycle 0->1->2->0. The cycle is detected when node 0 is found in the recursion stack during exploration from node 2.

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