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

Cycle Detection in Directed Graph

📖 Scenario: Imagine you are building a task manager app. Each task can depend on other tasks to be done first. You want to check if there is a circular dependency among tasks, which means some tasks depend on each other in a loop. This would make it impossible to finish the tasks.

🎯 Goal: You will create a program in Rust to detect if a directed graph (representing tasks and their dependencies) has a cycle. This helps find circular dependencies.

📋 What You'll Learn

Create a directed graph using an adjacency list with exact tasks and dependencies

Create a vector to track visited nodes

Implement a function to detect cycles using depth-first search (DFS)

Print whether the graph has a cycle or not

💡 Why This Matters

🌍 Real World

Detecting cycles in task dependencies helps avoid impossible schedules in project management software.

💼 Career

Cycle detection is a common problem in software engineering, useful in build systems, dependency management, and deadlock detection.

1

Create the directed graph using adjacency list

Create a variable called graph as a Vec> with 4 nodes. Use these exact edges: node 0 points to 1 and 2, node 1 points to 2, node 2 points to 0 and 3, node 3 points to no nodes.

DSA Rust

let graph: Vec> = vec![
    vec![],
    vec![],
    vec![],
    vec![],
];
// Your code here

Hint

Use vec![vec![...], vec![...], ...] to create the adjacency list with exact edges.

2

Create vectors to track visited and recursion stack

Create two vectors called visited and rec_stack of type Vec with length 4, initialized to false.

DSA Rust

let graph: Vec> = vec![
    vec![1, 2],
    vec![2],
    vec![0, 3],
    vec![],
];

let visited = vec![false; 4];
let rec_stack = vec![false; 4];
// Your code here

Hint

Use vec![false; 4] to create boolean vectors of size 4.

3

Implement DFS function to detect cycle

Write a function called is_cyclic that takes node: usize, graph: &Vec>, visited: &mut Vec, and rec_stack: &mut Vec. Use DFS to check if there is a cycle starting from node. Return true if a cycle is found, otherwise false. Mark visited[node] and rec_stack[node] as true when visiting. For each neighbor, if not visited, recursively call is_cyclic. If neighbor is in recursion stack, return true. After visiting neighbors, set rec_stack[node] to false.

DSA Rust

let graph: Vec> = vec![
    vec![1, 2],
    vec![2],
    vec![0, 3],
    vec![],
];

let mut visited = vec![false; 4];
let mut rec_stack = vec![false; 4];

fn is_cyclic(node: usize, graph: &Vec>, visited: &mut Vec, rec_stack: &mut Vec) -> bool {
    // Your code here
}

Hint

Use recursion and track nodes in the current path with rec_stack. Return true if a cycle is found.

4

Check all nodes and print if graph has a cycle

Use a for loop with variable node from 0 to 3. For each node, if visited[node] is false, call is_cyclic(node, &graph, &mut visited, &mut rec_stack). If it returns true, print exactly "Graph has a cycle" and return. If no cycles found, print exactly "Graph has no cycle".

DSA Rust

let graph: Vec> = vec![
    vec![1, 2],
    vec![2],
    vec![0, 3],
    vec![],
];

let mut visited = vec![false; 4];
let mut rec_stack = vec![false; 4];

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

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

for node in 0..4 {
    // Your code here
}

Hint

Loop over all nodes and call is_cyclic. Print the exact messages as instructed.

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