Cycle Detection in Directed Graph in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a cycle in a directed graph?

A cycle in a directed graph is a path that starts and ends at the same vertex, following the direction of edges, without repeating any vertex.

beginner

Which algorithm is commonly used to detect cycles in a directed graph?

Depth-First Search (DFS) with recursion stack tracking is commonly used to detect cycles in a directed graph.

intermediate

In cycle detection using DFS, what does it mean if a node is found in the recursion stack?

If a node is found in the recursion stack during DFS, it means a cycle exists because the node is being visited again before the previous visit finished.

intermediate

What are the two main data structures used in DFS-based cycle detection in directed graphs?

The two main data structures are: 1) a visited set to track visited nodes, and 2) a recursion stack to track nodes in the current DFS path.

advanced

Why can't we use simple visited flags alone to detect cycles in directed graphs?

Because a node might be visited multiple times in different paths, simple visited flags can't distinguish between nodes in the current path and nodes visited earlier, so recursion stack is needed.

What does a cycle in a directed graph imply?

A There is a path from a node back to itself following edge directions

B The graph is disconnected

C The graph has no edges

D All nodes have the same number of edges

A cycle means a path exists from a node back to itself following the direction of edges.

Which data structure helps track nodes currently in the DFS path for cycle detection?

A Queue

B Recursion stack

C Priority queue

D Hash map

The recursion stack tracks nodes in the current DFS path to detect cycles.

If a node is visited and not in the recursion stack, what does it mean for cycle detection?

A Cycle detected

B Node is isolated

C Graph is disconnected

D No cycle through this node in current path

If a node is visited but not in recursion stack, it means no cycle through this node in the current DFS path.

What is the time complexity of DFS-based cycle detection in a directed graph with V vertices and E edges?

A O(V + E)

B O(V^2)

C O(E^2)

D O(1)

DFS visits each vertex and edge once, so time complexity is O(V + E).

Which Rust feature helps avoid stack overflow in deep DFS recursion?

A Unsafe code

B Using global variables

C Iterative DFS using explicit stack

D Macros

Iterative DFS with an explicit stack avoids deep recursion and stack overflow.

Explain how DFS with recursion stack detects cycles in a directed graph.

Think about nodes currently being explored versus already explored.

Describe the difference between visited set and recursion stack in cycle detection.

One tracks all visits, the other tracks current path.

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