Cycle Detection in Directed Graph in DSA Rust

Mental Model

We want to find if following arrows in a graph leads us back to where we started, forming a loop.

Analogy: Imagine walking through a maze of one-way doors. If you ever return to a room you already visited on the same path, there is a cycle.

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

Dry Run Walkthrough

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

Goal: Detect if there is a cycle in the directed graph

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: Follow edge 0->1 to continue search

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

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

Why: Follow edge 1->2 to continue search

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

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

Why: Follow edge 2->3 to continue search

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

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

Why: Finding a node already in visiting means a cycle

Step 6: Cycle detected, stop search

Cycle found involving nodes 1,2,3

Why: We found a loop 1->2->3->1

Result:

Cycle detected in graph

Annotated Code

DSA Rust

use std::collections::HashMap;
use std::collections::HashSet;

struct Graph {
    edges: HashMap<usize, Vec<usize>>,
}

impl Graph {
    fn new() -> Self {
        Graph { edges: HashMap::new() }
    }

    fn add_edge(&mut self, from: usize, to: usize) {
        self.edges.entry(from).or_default().push(to);
    }

    fn has_cycle(&self) -> bool {
        let mut visiting = HashSet::new();
        let mut visited = HashSet::new();

        fn dfs(
            node: usize,
            graph: &HashMap<usize, Vec<usize>>,
            visiting: &mut HashSet<usize>,
            visited: &mut HashSet<usize>,
        ) -> bool {
            if visiting.contains(&node) {
                return true; // cycle found
            }
            if visited.contains(&node) {
                return false; // already checked no cycle here
            }

            visiting.insert(node); // mark node as visiting

            if let Some(neighbors) = graph.get(&node) {
                for &neighbor in neighbors {
                    if dfs(neighbor, graph, visiting, visited) {
                        return true; // cycle detected in recursion
                    }
                }
            }

            visiting.remove(&node); // done exploring node
            visited.insert(node); // mark node as fully visited
            false
        }

        for &node in self.edges.keys() {
            if dfs(node, &self.edges, &mut visiting, &mut visited) {
                return true; // cycle found
            }
        }
        false
    }
}

fn main() {
    let mut graph = Graph::new();
    graph.add_edge(0, 1);
    graph.add_edge(1, 2);
    graph.add_edge(2, 3);
    graph.add_edge(3, 1);

    if graph.has_cycle() {
        println!("Cycle detected in graph");
    } else {
        println!("No cycle detected");
    }
}

if visiting.contains(&node) { return true; }

Detect cycle if node is currently being visited in this path

if visited.contains(&node) { return false; }

Skip nodes already fully explored without cycles

visiting.insert(node);

Mark node as visiting before exploring neighbors

for &neighbor in neighbors { if dfs(neighbor, graph, visiting, visited) { return true; } }

Recursively visit neighbors to detect cycles

visiting.remove(&node); visited.insert(node);

Mark node as fully visited after exploring all neighbors

for &node in self.edges.keys() { if dfs(node, &self.edges, &mut visiting, &mut visited) { return true; } }

Start DFS from each node to cover disconnected parts

Output

Cycle detected in graph

Complexity Analysis

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

Space: O(V) for recursion stack and sets tracking visiting and visited nodes

vs Alternative: Compared to naive cycle detection that may re-check nodes multiple times, this approach avoids repeated work by marking visited nodes

Edge Cases

Empty graph with no nodes

No cycle detected as there are no edges

DSA Rust

for &node in self.edges.keys() { if dfs(node, &self.edges, &mut visiting, &mut visited) { return true; } }

Graph with single node and no edges

No cycle detected since no edges to form a loop

DSA Rust

if let Some(neighbors) = graph.get(&node) { for &neighbor in neighbors { ... } }

Graph with multiple disconnected components

Cycle detection runs DFS from each component to find any cycle

DSA Rust

for &node in self.edges.keys() { if dfs(node, &self.edges, &mut visiting, &mut visited) { return true; } }

When to Use This Pattern

When you see a problem asking if a directed graph has loops, reach for cycle detection using DFS with visiting and visited sets to track recursion state.

Common Mistakes

Mistake: Not distinguishing between nodes currently in recursion (visiting) and nodes fully explored (visited), causing false cycle detection.
Fix: Use two separate sets: one for nodes in current path (visiting) and one for nodes fully processed (visited).

Summary

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

Use when you need to find loops in directed graphs, such as dependency checks or scheduling.

The key insight is to mark nodes as visiting during recursion and detect cycles if you revisit a visiting node.

Practice

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

easy

A. If the graph has any isolated nodes

B. If the graph has equal number of nodes and edges

C. If the graph is fully connected

D. If 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 starting at a node and following edges in their direction to come back to the same node.

2. Step 2: Identify what cycle detection finds

   Cycle detection checks if such a path exists in the graph.

3. Final Answer:

   If there is a path that starts and ends at the same node following the direction of edges -> Option D

4. Quick Check:

   Cycle detection = path starting and ending at same node [OK]

Hint: Cycle means a path back to start following edge directions [OK]

Common Mistakes:

• Confusing cycle with connectivity
• Thinking cycle ignores edge directions
• Assuming cycle means isolated nodes

2. Which Rust data structure is best to keep track of nodes currently in the recursion stack during DFS for cycle detection?

easy

A. HashSet<i32>

B. Vec<bool>

C. Vec<i32>

D. HashMap

Solution

1. Step 1: Identify purpose of recursion stack tracking

   We need to mark nodes currently being explored to detect back edges indicating cycles.

2. Step 2: Choose data structure for boolean tracking

   Vec<bool> is efficient to mark true/false for each node index during DFS recursion.

3. Final Answer:

   Vec<bool> -> Option B

4. Quick Check:

   Use Vec<bool> to track recursion stack nodes [OK]

Hint: Use boolean vector to mark recursion stack nodes [OK]

Common Mistakes:

• Using HashMap when simple Vec<bool> suffices
• Using Vec<i32> which stores values, not boolean flags
• Using HashSet which is less efficient here

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

fn main() {
    let graph = vec![
        vec![1],    // 0 -> 1
        vec![2],    // 1 -> 2
        vec![0],    // 2 -> 0 forms a cycle
        vec![4],    // 3 -> 4
        vec![]      // 4 no outgoing edges
    ];
    println!("{}", has_cycle(&graph));
}

fn has_cycle(graph: &Vec) -> bool {
    let n = graph.len();
    let mut visited = vec![false; n];
    let mut rec_stack = vec![false; n];

    for node in 0..n {
        if !visited[node] && dfs(node, graph, &mut visited, &mut rec_stack) {
            return true;
        }
    }
    false
}

fn dfs(node: usize, graph: &Vec, visited: &mut Vec<bool>, rec_stack: &mut Vec<bool>) -> bool {
    visited[node] = true;
    rec_stack[node] = true;

    for &neighbor in &graph[node] {
        if !visited[neighbor] && dfs(neighbor, graph, visited, rec_stack) {
            return true;
        } else if rec_stack[neighbor] {
            return true;
        }
    }

    rec_stack[node] = false;
    false
}

medium

A. true

B. false

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Analyze graph edges for cycles

   Nodes 0->1, 1->2, 2->0 form a cycle because 2 points back to 0.

2. Step 2: Understand DFS cycle detection logic

   DFS marks nodes visited and tracks recursion stack. When it finds a neighbor in recursion stack, it returns true indicating cycle.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Cycle exists in 0->1->2->0 path = true [OK]

Hint: Cycle if DFS finds neighbor in recursion stack [OK]

Common Mistakes:

• Ignoring recursion stack check
• Assuming no cycle because graph is small
• Confusing visited with recursion stack

4. Identify the bug in this Rust DFS function for cycle detection in a directed graph:

fn dfs(node: usize, graph: &Vec, visited: &mut Vec<bool>, rec_stack: &mut Vec<bool>) -> bool {
    visited[node] = true;
    for &neighbor in &graph[node] {
        if !visited[neighbor] && dfs(neighbor, graph, visited, rec_stack) {
            return true;
        } else if rec_stack[neighbor] {
            return true;
        }
    }
    rec_stack[node] = false;
    false
}

medium

A. Function does not return a boolean

B. visited[node] is not set to true

C. rec_stack[node] is never set to true at start

D. Graph parameter type is incorrect

Solution

1. Step 1: Check recursion stack usage

   rec_stack[node] should be set to true when node is first visited to track recursion path.

2. Step 2: Identify missing line

   Code misses rec_stack[node] = true at start, so cycle detection via recursion stack fails.

3. Final Answer:

   rec_stack[node] is never set to true at start -> Option C

4. Quick Check:

   Set rec_stack[node] = true before DFS neighbors [OK]

Hint: Always mark node in recursion stack before DFS neighbors [OK]

Common Mistakes:

• Forgetting to mark recursion stack at start
• Confusing visited and recursion stack roles
• Not returning boolean properly

5. Given a directed graph represented as adjacency list:

let graph = vec![
    vec![1, 2],  // 0 -> 1, 0 -> 2
    vec![3],     // 1 -> 3
    vec![3],     // 2 -> 3
    vec![4],     // 3 -> 4
    vec![1]      // 4 -> 1 creates a cycle
];

Which nodes are part of the cycle detected by DFS cycle detection?

hard

A. [1, 3, 4]

B. [0, 1, 2]

C. [0, 4]

D. [2, 3, 4]

Solution

1. Step 1: Trace cycle path in graph

   Edges 1->3, 3->4, 4->1 form a cycle involving nodes 1, 3, and 4.

2. Step 2: Confirm nodes in cycle

   Node 0 and 2 are not in cycle because they lead into cycle but not part of cycle loop.

3. Final Answer:

   [1, 3, 4] -> Option A

4. Quick Check:

   Cycle nodes = 1, 3, 4 [OK]

Hint: Cycle nodes form closed loop edges [OK]

Common Mistakes:

• Including nodes that only lead to cycle
• Missing nodes that complete the cycle
• Confusing cycle with path