Cycle Detection in Directed Graph in DSA C# - 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 DFS on neighbor

↓

Remove node from recursion stack

↓

Continue or finish

Start DFS from each node, track visited and recursion stack to find back edges indicating cycles.

Execution Sample

DSA C#

bool DFS(int node) {
  visited[node] = true;
  recStack[node] = true;
  foreach (var neighbor in graph[node]) {
    if (!visited[neighbor] && DFS(neighbor)) return true;
    else if (recStack[neighbor]) return true;
  }
  recStack[node] = false;
  return false;
}

DFS visits nodes marking recursion stack to detect cycles by back edges.

Execution Table

Step	Operation	Current Node	Visited Set	Recursion Stack	Action	Cycle Detected	Graph State
1	Start DFS	0	[0]	[0]	Mark node 0 visited and in recursion stack	No	0 -> [1,2], 1 -> [2], 2 -> [0,3], 3 -> []
2	Visit neighbor	1	[0,1]	[0,1]	Node 1 not visited, recurse DFS(1)	No	Same
3	Visit neighbor	2	[0,1,2]	[0,1,2]	Node 2 not visited, recurse DFS(2)	No	Same
4	Visit neighbor	0	[0,1,2]	[0,1,2]	Node 0 visited and in recursion stack	Yes	Cycle detected via edge 2->0
5	Return true	2	[0,1,2]	[0,1,2]	Cycle found, propagate true	Yes	Same
6	Return true	1	[0,1,2]	[0,1,2]	Cycle found, propagate true	Yes	Same
7	Return true	0	[0,1,2]	[0,1,2]	Cycle found, propagate true	Yes	Same
8	End	-	[0,1,2]	[0,1,2]	DFS ends, cycle detected	Yes	Same

💡 Cycle detected at step 4 when visiting node 0 already in recursion stack

Variable Tracker

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

Key Moments - 3 Insights

Why do we need a recursion stack separate from the visited set?

The recursion stack tracks nodes currently in the path of DFS. If we find a neighbor in this stack (see step 4), it means a cycle exists. The visited set alone can't detect this because it only shows if a node was ever visited.

What happens if a node is visited but not in the recursion stack?

If a node is visited but not in the recursion stack, it means we finished exploring it and no cycle was found through it. So encountering such a node does not indicate a cycle (see steps 5-7).

Why do we remove nodes from the recursion stack after DFS call?

Removing nodes from the recursion stack means we finished exploring all paths from that node. This prevents false cycle detection when backtracking.

Visual Quiz - 3 Questions

Look at the execution table, what is the recursion stack after step 3?

A [0,1,2]

B [true,true,false,false]

C [true,true,true,false]

D [false,false,false,false]

💡 Hint

Check the 'Recursion Stack' column at step 3 in the execution_table.

At which step does the cycle get detected?

A Step 6

B Step 2

C Step 4

D Step 8

💡 Hint

Look for 'Cycle Detected' column showing 'Yes' for the first time.

If we remove the recursion stack check, what would happen?

A Cycle detection would still work correctly

B False positives for cycles might occur

C No cycles would be detected

D The algorithm would run faster

💡 Hint

Refer to the key moment explaining why recursion stack is needed.

Concept Snapshot

Cycle Detection in Directed Graph using DFS
- Use two arrays: visited and recursion stack
- Mark node visited and add to recursion stack on DFS entry
- If neighbor is in recursion stack, cycle found
- Remove node from recursion stack on DFS exit
- Returns true if cycle detected, else false

Full Transcript

Cycle detection in a directed graph uses depth-first search (DFS). We keep track of nodes visited and nodes currently in the recursion stack (the current DFS path). Starting from each unvisited node, we mark it visited and add it to the recursion stack. For each neighbor, if it is not visited, we recurse DFS on it. If it is already in the recursion stack, a cycle is detected. After exploring neighbors, we remove the node from the recursion stack. This method detects cycles by finding back edges to nodes in the current path. The execution table shows step-by-step how nodes are visited, recursion stack changes, and when the cycle is detected. Key moments clarify why the recursion stack is essential and how it differs from the visited set. The visual quiz tests understanding of recursion stack state, detection step, and consequences of removing the recursion stack check.

Practice

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

easy

A. Whether there is a path that starts and ends at the same vertex following edge directions

B. The shortest path between two vertices

C. The total number of vertices in the graph

D. The maximum degree of any vertex

Solution

1. Step 1: Understand cycle in directed graph

   A cycle means a path that starts and ends at the same vertex following the direction of edges.

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 vertex following edge directions -> Option A

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 vertex

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

easy

A. Queue

B. Stack or boolean array to mark recursion stack

C. Dictionary

D. LinkedList

Solution

1. Step 1: Recall DFS cycle detection method

   During DFS, we track nodes in the current recursion path to detect back edges.

2. Step 2: Identify data structure used

   This is done using a stack or a boolean array marking nodes in the recursion stack.

3. Final Answer:

   Stack or boolean array to mark recursion stack -> Option B

4. Quick Check:

   Recursion stack tracking = Stack/boolean array [OK]

Hint: Use stack or boolean array to track recursion path [OK]

Common Mistakes:

• Using queue which is FIFO, not suitable for recursion stack
• Confusing dictionary with recursion tracking
• Not marking nodes currently in recursion

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

var graph = new Dictionary<int, List<int>> {
  {1, new List<int>{2}},
  {2, new List<int>{3}},
  {3, new List<int>{1}}
};
bool HasCycle(int node, HashSet<int> visited, HashSet<int> recStack) {
  if (!visited.Contains(node)) {
    visited.Add(node);
    recStack.Add(node);
    foreach (var neighbor in graph[node]) {
      if (!visited.Contains(neighbor) && HasCycle(neighbor, visited, recStack))
        return true;
      else if (recStack.Contains(neighbor))
        return true;
    }
  }
  recStack.Remove(node);
  return false;
}

var visited = new HashSet<int>();
var recStack = new HashSet<int>();
Console.WriteLine(HasCycle(1, visited, recStack));

medium

A. False

B. Compilation error

C. Runtime exception

D. True

Solution

1. Step 1: Analyze graph edges

   The graph has edges 1->2, 2->3, and 3->1 forming a cycle.

2. Step 2: Trace DFS cycle detection

   Starting at node 1, recursion visits 2, then 3, then back to 1 which is in recursion stack, so cycle detected.

3. Final Answer:

   True -> Option D

4. Quick Check:

   Cycle exists in graph = True [OK]

Hint: Cycle if recursion stack revisits a node [OK]

Common Mistakes:

• Ignoring recursion stack check
• Assuming no cycle because graph looks simple
• Confusing visited set with recursion stack

4. Identify the bug in this C# DFS cycle detection code snippet:

bool HasCycle(int node, HashSet<int> visited, HashSet<int> recStack) {
  visited.Add(node);
  foreach (var neighbor in graph[node]) {
    if (!visited.Contains(neighbor) && HasCycle(neighbor, visited, recStack))
      return true;
    else if (recStack.Contains(neighbor))
      return true;
  }
  recStack.Remove(node);
  return false;
}

medium

A. Missing removing node from visited after recursion

B. Incorrect use of HashSet instead of List

C. Missing adding node to recStack before recursion

D. No bug, code is correct

Solution

1. Step 1: Check recursion stack usage

   Node must be added to recStack before exploring neighbors to detect back edges.

2. Step 2: Identify missing step

   Code adds node to visited but never adds to recStack before recursion, so cycle detection fails.

3. Final Answer:

   Missing adding node to recStack before recursion -> Option C

4. Quick Check:

   recStack update missing = bug [OK]

Hint: Always add node to recursion stack before DFS call [OK]

Common Mistakes:

• Forgetting to add node to recursion stack
• Removing node from visited incorrectly
• Confusing visited and recursion stack roles

5. Given a directed graph represented as adjacency list:

var graph = new Dictionary<int, List<int>> {
  {1, new List<int>{2, 3}},
  {2, new List<int>{4}},
  {3, new List<int>{4}},
  {4, new List<int>{5}},
  {5, new List<int>{3}}
};

Which nodes form a cycle in this graph?

hard

A. Nodes 3, 4, 5

B. Nodes 1, 2, 4

C. Nodes 2, 3, 5

D. No cycle exists

Solution

1. Step 1: Trace edges to find cycle

   Edges: 3->4, 4->5, 5->3 form a cycle among nodes 3, 4, 5.

2. Step 2: Confirm cycle presence

   Starting at 3, path 3->4->5->3 loops back, confirming cycle.

3. Final Answer:

   Nodes 3, 4, 5 -> Option A

4. Quick Check:

   Cycle nodes = 3,4,5 [OK]

Hint: Follow edges to see if path loops back to start [OK]

Common Mistakes:

• Ignoring edge 5->3 that closes cycle
• Assuming no cycle because 1 and 2 are acyclic
• Confusing cycle nodes with all connected nodes