Cycle Detection in Directed Graph in DSA Go - 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

↓

Remove node from recursion stack

↓

Continue

↓

No cycle found

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

Execution Sample

DSA Go

func dfs(node int) bool {
  visited[node] = true
  recStack[node] = true
  for _, neighbor := range graph[node] {
    if !visited[neighbor] {
      if dfs(neighbor) {
        return true
      }
    } else if recStack[neighbor] {
      return true
    }
  }
  recStack[node] = false
  return false
}

This code runs DFS to detect cycles by tracking nodes in the current recursion stack.

Execution Table

Step	Operation	Current Node	Visited Set	Recursion Stack	Action	Cycle Detected	Graph State
1	Start DFS	0	[0]	[0]	Mark 0 visited and in stack	No	0 -> [1,2], 1 -> [2], 2 -> [0,3], 3 -> []
2	Visit neighbor	1	[0,1]	[0,1]	Mark 1 visited and in stack	No	Same
3	Visit neighbor	2	[0,1,2]	[0,1,2]	Mark 2 visited and in stack	No	Same
4	Visit neighbor	0	[0,1,2]	[0,1,2]	0 is in recursion stack	Yes	Cycle detected via edge 2->0
5	Backtrack	2	[0,1,2]	[0,1]	Remove 2 from recursion stack	Yes	Cycle confirmed
6	Backtrack	1	[0,1,2]	[0]	Remove 1 from recursion stack	Yes	Cycle confirmed
7	Backtrack	0	[0,1,2]	[]	Remove 0 from recursion stack	Yes	Cycle confirmed
8	DFS ends	-	[0,1,2]	[]	Cycle found, stop	Yes	Final graph state unchanged

💡 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 5	After Step 6	After Step 7	Final
visited	[]	[0]	[0,1]	[0,1,2]	[0,1,2]	[0,1,2]	[0,1,2]	[0,1,2]	[0,1,2]
recStack	[]	[0]	[0,1]	[0,1,2]	[0,1,2]	[0,1]	[0]	[]	[]
currentNode	-	0	1	2	0	2	1	0	-
cycleDetected	false	false	false	false	true	true	true	true	true

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 explored before, but being in the recursion stack means we are still exploring it in the current path, indicating a back edge and thus a cycle. See step 4 in execution_table where visiting node 0 again in recStack triggers cycle detection.

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

Removing nodes from the recursion stack means we finished exploring all paths from that node. This prevents false cycle detection from nodes that are fully processed. See steps 5-7 where nodes are removed from recStack after recursion.

What happens if the graph has no edges?

If there are no edges, DFS visits each node once, no neighbors to recurse on, so no cycles are detected. The recursion stack is cleared immediately after each node. This is implied by the flow and absence of cycle detection in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the state of the recursion stack?

A [1,2]

B [0,1,2]

C [0,1]

D []

💡 Hint

Check the 'Recursion Stack' column at step 4 in execution_table

At which step does the cycle get detected?

A Step 2

B Step 6

C Step 4

D Step 8

💡 Hint

Look at the 'Cycle Detected' column in execution_table to find when it first becomes 'Yes'

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

A False positives for cycles may occur

B Cycle detection would still work correctly

C The algorithm would run faster

D No nodes would be visited

💡 Hint

Refer to key_moments explanation about why recursion stack is needed

Concept Snapshot

Cycle Detection in Directed Graph using DFS:
- Use two arrays: visited[] and recStack[]
- DFS marks node visited and adds to recStack
- If neighbor in recStack, cycle found
- Remove node from recStack after recursion
- Stops on first cycle detected

Full Transcript

Cycle detection in a directed graph uses depth-first search (DFS). We start DFS from each unvisited node. When visiting a node, we mark it as visited and add it to a recursion stack to track the current path. For each neighbor, if it is not visited, we recurse on it. If the neighbor is already in the recursion stack, it means we found a back edge, indicating a cycle. After exploring all neighbors, we remove the node from the recursion stack. This process continues until a cycle is found or all nodes are processed. The recursion stack helps distinguish between nodes visited in the current path and those fully processed, preventing false cycle detection.

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 node following the direction of edges

B. The shortest path between two nodes

C. The total number of nodes in the graph

D. The maximum degree of any node

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 A

4. Quick Check:

   Cycle detection = finding directed loops [OK]

Hint: Cycle means a loop following edge directions [OK]

Common Mistakes:

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

2. Which of the following Go code snippets correctly declares a graph as an adjacency list for cycle detection?

easy

A. graph := make(map[int][]int)

B. graph := []int{}

C. graph := map[int]int{}

D. graph := [][]int{}

Solution

1. Step 1: Understand adjacency list representation

   An adjacency list for a directed graph maps each node to a list of nodes it points to.

2. Step 2: Check Go syntax for adjacency list

   Using map[int][]int creates a map from int to slice of ints, perfect for adjacency list.

3. Final Answer:

   graph := make(map[int][]int) -> Option A

4. Quick Check:

   Adjacency list = map[int][]int [OK]

Hint: Adjacency list uses map of int to slice of int [OK]

Common Mistakes:

• Using slice of int only (no mapping)
• Using map[int]int which stores single int per node
• Using [][]int without map keys

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

package main
import "fmt"

func dfs(node int, graph map[int][]int, visited, recStack map[int]bool) bool {
    if recStack[node] {
        return true
    }
    if visited[node] {
        return false
    }
    visited[node] = true
    recStack[node] = true
    for _, neighbor := range graph[node] {
        if dfs(neighbor, graph, visited, recStack) {
            return true
        }
    }
    recStack[node] = false
    return false
}

func main() {
    graph := map[int][]int{
        1: {2},
        2: {3},
        3: {1},
    }
    visited := make(map[int]bool)
    recStack := make(map[int]bool)
    fmt.Println(dfs(1, graph, visited, recStack))
}

medium

A. false

B. true

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Analyze graph structure

   Graph edges: 1->2, 2->3, 3->1 form a cycle.

2. Step 2: Trace DFS cycle detection

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

3. Final Answer:

   true -> Option B

4. Quick Check:

   Cycle detected = true [OK]

Hint: Cycle if node revisited in recursion stack [OK]

Common Mistakes:

• Ignoring recursion stack for cycle detection
• Assuming visited alone detects cycle
• Confusing false with no cycle

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

func dfs(node int, graph map[int][]int, visited map[int]bool) bool {
    if visited[node] {
        return true
    }
    visited[node] = true
    for _, neighbor := range graph[node] {
        if dfs(neighbor, graph, visited) {
            return true
        }
    }
    return false
}

medium

A. Return type should be int, not bool

B. Visited map should be a slice, not a map

C. Missing recursion stack to track nodes in current path

D. Graph should be a slice of slices, not a map

Solution

1. Step 1: Understand cycle detection logic

   Cycle detection in directed graph needs to track nodes in current recursion path (recursion stack).

2. Step 2: Identify missing recursion stack

   This code only uses visited to mark visited nodes, which cannot detect cycles correctly in directed graphs.

3. Final Answer:

   Missing recursion stack to track nodes in current path -> Option C

4. Quick Check:

   Recursion stack needed for directed cycle detection [OK]

Hint: Use recursion stack to detect back edges [OK]

Common Mistakes:

• Using only visited to detect cycles
• Confusing undirected and directed cycle detection
• Ignoring recursion stack leads to false negatives

5. Given a directed graph represented as adjacency list:

graph := map[int][]int{
    1: {2, 3},
    2: {4},
    3: {4, 5},
    4: {6},
    5: {6},
    6: {3},
}

Which nodes are part of a cycle in this graph?

hard

A. [1, 3, 5]

B. [1, 2, 5]

C. [2, 4, 5]

D. [3, 4, 6]

Solution

1. Step 1: Analyze edges for cycles

   Edges: 3->4, 4->6, 6->3 form a cycle involving nodes 3, 4, 6.

2. Step 2: Confirm cycle nodes

   Nodes 1, 2, 5 lead into cycle but are not part of cycle themselves.

3. Final Answer:

   [3, 4, 6] -> Option D

4. Quick Check:

   Cycle nodes = [3,4,6] [OK]

Hint: Trace back edges to find cycle nodes [OK]

Common Mistakes:

• Including nodes that only lead to cycle
• Missing nodes that form the cycle
• Confusing cycle membership with reachability