Cycle Detection in Directed Graph in DSA Go

Mental Model

We want to find if there is a loop in a directed graph by tracking nodes we are currently visiting and nodes we have fully checked.

Analogy: Imagine walking through a maze where some paths lead back to where you started. If you step on a tile you are already standing on in this walk, you found a loop.

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

Here, node 3 points back to 0, forming a cycle.

Dry Run Walkthrough

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

Goal: Detect if the graph contains a cycle

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: Continue DFS to next connected node

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

visiting: {0,1,2}, visited: {}

Why: Keep exploring deeper to find cycles

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

visiting: {0,1,2,3}, visited: {}

Why: Explore next node in path

Step 5: From node 3, try to move to node 0 which is already visiting

visiting: {0,1,2,3}, visited: {}

Why: Finding a node currently being visited means a cycle

Step 6: Cycle detected, stop search

Cycle found involving nodes 0,1,2,3

Why: Cycle confirmed by revisiting a node in current path

Result:

Cycle found: 0 -> 1 -> 2 -> 3 -> 0

Annotated Code

DSA Go

package main

import "fmt"

// Graph represents a directed graph using adjacency list
type Graph struct {
	adj map[int][]int
}

// NewGraph creates a new graph
func NewGraph() *Graph {
	return &Graph{adj: make(map[int][]int)}
}

// AddEdge adds a directed edge from u to v
func (g *Graph) AddEdge(u, v int) {
	g.adj[u] = append(g.adj[u], v)
}

// hasCycleUtil performs DFS to detect cycle
func (g *Graph) hasCycleUtil(node int, visiting, visited map[int]bool) bool {
	if visiting[node] {
		return true // cycle found
	}
	if visited[node] {
		return false // already checked no cycle here
	}

	visiting[node] = true // mark node as visiting
	for _, neighbor := range g.adj[node] {
		if g.hasCycleUtil(neighbor, visiting, visited) {
			return true
		}
	}
	visiting[node] = false // done visiting this node
	visited[node] = true   // mark node as fully visited
	return false
}

// HasCycle checks if the graph contains a cycle
func (g *Graph) HasCycle() bool {
	visiting := make(map[int]bool)
	visited := make(map[int]bool)
	for node := range g.adj {
		if !visited[node] {
			if g.hasCycleUtil(node, visiting, visited) {
				return true
			}
		}
	}
	return false
}

func main() {
	g := NewGraph()
	g.AddEdge(0, 1)
	g.AddEdge(1, 2)
	g.AddEdge(2, 3)
	g.AddEdge(3, 0) // cycle edge

	if g.HasCycle() {
		fmt.Println("Cycle found: 0 -> 1 -> 2 -> 3 -> 0")
	} else {
		fmt.Println("No cycle found")
	}
}

if visiting[node] { return true }

Detect cycle if node is currently being visited

if visited[node] { return false }

Skip nodes already fully checked

visiting[node] = true

Mark node as currently visiting to track recursion stack

for _, neighbor := range g.adj[node] { if g.hasCycleUtil(neighbor, visiting, visited) { return true } }

Recursively visit all neighbors to find cycles

visiting[node] = false; visited[node] = true

Mark node done visiting and fully visited

for node := range g.adj { if !visited[node] { if g.hasCycleUtil(node, visiting, visited) { return true } } }

Start DFS from all unvisited nodes to cover disconnected graph

Output

Cycle found: 0 -> 1 -> 2 -> 3 -> 0

Complexity Analysis

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

Space: O(V) for recursion stack and visited maps to track nodes

vs Alternative: Naive cycle detection by checking all paths repeatedly is O(V * E), so DFS with visiting sets is more efficient

Edge Cases

Empty graph with no nodes

No cycle found since graph is empty

DSA Go

for node := range g.adj { if !visited[node] { ... } }

Graph with single node and no edges

No cycle found because no edges to form a loop

DSA Go

for node := range g.adj { if !visited[node] { ... } }

Graph with multiple disconnected components, one with cycle

Cycle detected because DFS covers all components

DSA Go

for node := range g.adj { if !visited[node] { ... } }

When to Use This Pattern

When you need to find if a directed graph has loops, use DFS with visiting and visited sets to detect cycles efficiently.

Common Mistakes

Mistake: Not distinguishing between nodes currently in recursion stack and fully visited nodes
Fix: Use separate 'visiting' and 'visited' sets to track recursion stack and completed nodes

Mistake: Not running DFS from all nodes, missing disconnected components
Fix: Run DFS from every unvisited node in the graph

Summary

Detects if a directed graph contains a cycle by DFS tracking nodes in current path.

Use when you must find loops in directed graphs to avoid infinite processing or invalid states.

The key insight is to track nodes currently being visited separately from those fully checked.

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