Cycle Detection in Directed Graph in DSA Go - Build from Scratch

Cycle Detection in Directed Graph

📖 Scenario: Imagine you are building a task scheduler that needs to check if there are any circular dependencies between tasks. Each task depends on other tasks to be completed first. If there is a cycle, the scheduler cannot proceed.

🎯 Goal: You will create a directed graph representing tasks and their dependencies, then write code to detect if there is a cycle in the graph.

📋 What You'll Learn

Create a directed graph using a map where keys are task names (strings) and values are slices of dependent task names.

Add a helper map to track visited tasks during traversal.

Implement a function to detect cycles using Depth-First Search (DFS) with recursion and track recursion stack.

Print whether the graph contains a cycle or not.

💡 Why This Matters

🌍 Real World

Cycle detection is crucial in task scheduling, dependency resolution, and deadlock detection in operating systems.

💼 Career

Understanding graph cycle detection is important for software engineers working on compilers, build systems, and complex workflow automation.

1

Create the Directed Graph

Create a variable called graph of type map[string][]string with these exact entries: "A": {"B"}, "B": {"C"}, "C": {"A"}, "D": {"E"}, "E": {}

DSA Go

# Your code here

Hint

Use a map with string keys and slice of strings as values to represent the graph.

2

Add Visited and Recursion Stack Maps

Add two variables called visited and recStack of type map[string]bool initialized as empty maps to track visited nodes and recursion stack respectively.

DSA Go

package main

import "fmt"

func main() {
    graph := map[string][]string{
        "A": {"B"},
        "B": {"C"},
        "C": {"A"},
        "D": {"E"},
        "E": {},
    }
    // Your code here
}

Hint

Use make(map[string]bool) to create empty maps for visited and recStack.

3

Implement Cycle Detection Function

Write a function called isCyclic that takes parameters node string, graph map[string][]string, visited map[string]bool, and recStack map[string]bool. It returns bool. Use DFS to detect a cycle: if node is not visited, mark it visited and add to recStack. For each neighbor, recursively call isCyclic. If neighbor is in recStack, return true. Remove node from recStack before returning false.

DSA Go

package main

import "fmt"

func main() {
    graph := map[string][]string{
        "A": {"B"},
        "B": {"C"},
        "C": {"A"},
        "D": {"E"},
        "E": {},
    }
    visited := make(map[string]bool)
    recStack := make(map[string]bool)
}

// Your code here

Hint

Use recursion and track nodes in the recursion stack to detect cycles.

4

Check and Print if Graph Contains Cycle

In main, iterate over each node in graph. For each node, if it is not visited, call isCyclic with the node, graph, visited, and recStack. If isCyclic returns true, print "Graph contains a cycle" and return. If no cycles found, print "Graph does not contain a cycle".

DSA Go

package main

import "fmt"

func isCyclic(node string, graph map[string][]string, visited map[string]bool, recStack map[string]bool) bool {
    if !visited[node] {
        visited[node] = true
        recStack[node] = true

        for _, neighbor := range graph[node] {
            if !visited[neighbor] && isCyclic(neighbor, graph, visited, recStack) {
                return true
            } else if recStack[neighbor] {
                return true
            }
        }
    }
    recStack[node] = false
    return false
}

func main() {
    graph := map[string][]string{
        "A": {"B"},
        "B": {"C"},
        "C": {"A"},
        "D": {"E"},
        "E": {},
    }
    visited := make(map[string]bool)
    recStack := make(map[string]bool)
    // Your code here
}

Hint

Loop over all nodes and call isCyclic. Print the result accordingly.

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