Cycle Detection in Directed Graph in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the visited vector with false values.

DSA Rust

let mut visited = [1][false; graph.len()];

Drag options to blanks, or click blank then click option'

Avec!

Bwith_capacity

Cresize

Ddefault

Attempts:

3 left

💡 Hint

Common Mistakes

Using vec::new() without initializing values

Using with_capacity which only reserves space but does not fill values

The vec! macro with [value; size] creates a vector initialized with the value repeated size times. Here, vec![false; graph.len()] initializes the vector with false values.

2fill in blank

medium

Complete the code to mark the current node as visited in the DFS function.

DSA Rust

visited[[1]] = true;

Drag options to blanks, or click blank then click option'

Agraph

Bstack

Cnode

Dindex

Attempts:

3 left

💡 Hint

Common Mistakes

Using graph or stack as index which are not integers

Using index which is undefined in this context

We mark the current node as visited by setting visited[node] to true.

3fill in blank

hard

Fix the error in the condition to detect a cycle when a node is in the recursion stack.

DSA Rust

if rec_stack[[1]] { return true; }

Drag options to blanks, or click blank then click option'

Agraph

Bvisited

Cnode

Dneighbor

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'node' instead of 'neighbor' which checks the wrong node

Using 'graph' or 'visited' which are not boolean vectors for recursion stack

We check if the neighbor node is already in the recursion stack to detect a cycle.

4fill in blank

hard

Fill both blanks to complete the loop that iterates over neighbors of the current node.

DSA Rust

for &[1] in graph[[2]].iter() {

Drag options to blanks, or click blank then click option'

Aneighbor

Bnode

Cedge

Dindex

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'edge' which is not defined

Using 'index' which is ambiguous here

The loop iterates over neighbors of the current node. We use 'neighbor' for each adjacent node and 'node' as the current node index.

5fill in blank

hard

Fill all three blanks to complete the recursive DFS call and update recursion stack.

DSA Rust

rec_stack[[1]] = true;
if dfs(graph, [2], visited, rec_stack) {
    return true;
}
rec_stack[[3]] = false;

Drag options to blanks, or click blank then click option'

Aneighbor

Bnode

Dvisited

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'node' instead of 'neighbor' causing wrong recursion

Not resetting recursion stack after recursion

We mark the neighbor as in recursion stack, call DFS on neighbor, and then remove neighbor from recursion stack after the call.

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