Cycle Detection in Directed Graph in DSA Rust - Execution Trace

Concept Flow - Cycle Detection in Directed Graph

Start DFS at a node

↓

Mark node as visiting

↓

For each neighbor

↓

Is neighbor visiting?

Yes→Cycle detected

No↓

Is neighbor visited?

No→DFS on neighbor

↓

After all neighbors

↓

Mark node as visited

↓

Backtrack or finish

Start DFS from each node, mark nodes as visiting during traversal. If a visiting node is found again, a cycle exists. Mark nodes visited after exploring neighbors.

Execution Sample

DSA Rust

fn dfs(node: usize, graph: &Vec<Vec<usize>>, state: &mut Vec<u8>) -> bool {
    if state[node] == 1 { return true; }
    if state[node] == 2 { return false; }
    state[node] = 1;
    for &neighbor in &graph[node] {
        if dfs(neighbor, graph, state) { return true; }
    }
    state[node] = 2;
    false
}

This DFS function detects cycles by marking nodes as visiting (1) and visited (2). If a visiting node is revisited, it returns true indicating a cycle.

Execution Table

Step	Operation	Current Node	State Vector	Action	Cycle Detected	Visual State
1	Start DFS at node 0	0	[0,0,0,0]	Mark node 0 as visiting	No	0(Visiting) -> 1(Unvisited) -> 2(Unvisited) -> 3(Unvisited)
2	Visit neighbor 1	1	[1,0,0,0]	Mark node 1 as visiting	No	0(Visiting) -> 1(Visiting) -> 2(Unvisited) -> 3(Unvisited)
3	Visit neighbor 2	2	[1,1,0,0]	Mark node 2 as visiting	No	0(Visiting) -> 1(Visiting) -> 2(Visiting) -> 3(Unvisited)
4	Visit neighbor 0	0	[1,1,1,0]	Node 0 is visiting -> cycle detected	Yes	Cycle found at node 0 revisited while visiting
5	Backtrack from node 2	2	[1,1,2,0]	Mark node 2 as visited	Yes	0(Visiting) -> 1(Visiting) -> 2(Visited) -> 3(Unvisited)
6	Backtrack from node 1	1	[1,2,2,0]	Mark node 1 as visited	Yes	0(Visiting) -> 1(Visited) -> 2(Visited) -> 3(Unvisited)
7	Backtrack from node 0	0	[2,2,2,0]	Mark node 0 as visited	Yes	0(Visited) -> 1(Visited) -> 2(Visited) -> 3(Unvisited)
8	Start DFS at node 3	3	[2,2,2,0]	Mark node 3 as visiting	Yes	0(Visited) -> 1(Visited) -> 2(Visited) -> 3(Visiting)
9	No neighbors for node 3	3	[2,2,2,1]	Mark node 3 as visited	Yes	0(Visited) -> 1(Visited) -> 2(Visited) -> 3(Visited)
10	All nodes processed	-	[2,2,2,2]	DFS complete	Yes	Cycle detected in graph

💡 DFS revisited a node marked as visiting at step 4, confirming a cycle in the graph.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	Final
state	[0,0,0,0]	[1,0,0,0]	[1,1,0,0]	[1,1,1,0]	[1,1,1,0]	[1,1,2,0]	[1,2,2,0]	[2,2,2,0]	[2,2,2,1]	[2,2,2,2]	[2,2,2,2]
current_node	-	0	1	2	0	2	1	0	3	3	-
cycle_detected	No	No	No	No	Yes	Yes	Yes	Yes	Yes	Yes	Yes

Key Moments - 3 Insights

Why do we mark nodes as 'visiting' before exploring neighbors?

Marking nodes as 'visiting' (state=1) helps detect cycles by identifying if we revisit a node currently in the call stack. See execution_table step 4 where revisiting node 0 marked as visiting detects a cycle.

What is the difference between 'visiting' and 'visited' states?

'Visiting' means the node is currently in the recursion stack (being explored). 'Visited' means all neighbors are explored and no cycle found from that node. This is shown in execution_table steps 5-7 where nodes change from visiting to visited.

Why does the DFS stop immediately when a cycle is detected?

Once a cycle is found (step 4), the function returns true immediately to avoid unnecessary work. This early exit is crucial for efficiency and correctness.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the state of node 0?

A Visiting

B Visited

C Unvisited

D Not in graph

💡 Hint

Check the 'State Vector' column at step 4 in execution_table; node 0 is marked as visiting (1).

At which step does the DFS mark node 2 as visited?

A Step 3

B Step 5

C Step 7

D Step 9

💡 Hint

Look at the 'Action' column in execution_table; node 2 is marked visited at step 5.

If the graph had no cycles, what would be the final value of 'cycle_detected' in variable_tracker?

A Yes

B Maybe

C No

D Undefined

💡 Hint

Refer to the 'cycle_detected' row in variable_tracker; it would remain 'No' if no cycle is found.

Concept Snapshot

Cycle Detection in Directed Graph using DFS:
- Use DFS to explore nodes.
- Mark nodes as visiting (1) when exploring.
- If a visiting node is found again, cycle exists.
- Mark nodes visited (2) after all neighbors.
- Return true immediately on cycle detection.
- State vector tracks node status: 0=unvisited,1=visiting,2=visited.

Full Transcript

Cycle detection in a directed graph uses depth-first search (DFS). We start DFS from each node, marking it as visiting. When we explore neighbors, if we find a node already marked visiting, it means a cycle exists. After exploring all neighbors, we mark the node as visited. The state vector tracks each node's status: unvisited, visiting, or visited. The DFS stops immediately when a cycle is detected. This method efficiently detects cycles by tracking recursion stack nodes and prevents revisiting fully explored nodes.

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