Cycle Detection in Directed Graph in DSA Rust - Time & Space Complexity

Time Complexity: Cycle Detection in Directed Graph

O(n + e)

Understanding Time Complexity

We want to understand how the time needed to find a cycle in a directed graph changes as the graph grows.

Specifically, how the number of nodes and edges affects the work done.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn dfs(node: usize, graph: &Vec<Vec<usize>>, 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] {
            if dfs(neighbor, graph, visited, rec_stack) {
                return true;
            }
        } else if rec_stack[neighbor] {
            return true;
        }
    }
    rec_stack[node] = false;
    false
}

fn has_cycle(graph: &Vec<Vec<usize>>) -> 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] {
            if dfs(node, graph, &mut visited, &mut rec_stack) {
                return true;
            }
        }
    }
    false
}
    

This code checks if a directed graph has a cycle by visiting nodes depth-first and tracking recursion stack.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Depth-first search (DFS) visits each node and its edges once.
• How many times: Each node is visited once, and each edge is checked once during recursion.

How Execution Grows With Input

As the graph grows with more nodes (n) and edges (e), the DFS explores all nodes and edges once.

Input Size (n, e)	Approx. Operations
10 nodes, 15 edges	About 25 operations (visiting nodes + edges)
100 nodes, 200 edges	About 300 operations
1000 nodes, 5000 edges	About 6000 operations

Pattern observation: The work grows roughly in proportion to the sum of nodes and edges.

Final Time Complexity

Time Complexity: O(n + e)

This means the time to detect a cycle grows linearly with the number of nodes plus edges in the graph.

Common Mistake

[X] Wrong: "Cycle detection takes quadratic time because of recursion inside loops."

[OK] Correct: Each node and edge is visited only once due to tracking visited nodes, so the recursion does not repeat work unnecessarily.

Interview Connect

Understanding this time complexity helps you explain how graph traversal algorithms scale and why tracking visited nodes is important.

Self-Check

"What if we used an adjacency matrix instead of adjacency lists? How would the time complexity change?"

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