Cycle Detection in Undirected Graph in DSA Rust - Execution Trace

Concept Flow - Cycle Detection in Undirected Graph

Start at any node

↓

Mark node as visited

↓

For each neighbor

↓

If neighbor not visited

↓

Recurse DFS

↓

Cycle found

↓

Done

Start DFS from any node, mark visited, explore neighbors. If a visited neighbor is not the parent, a cycle exists.

Execution Sample

DSA Rust

fn dfs(node: usize, parent: Option<usize>, graph: &Vec<Vec<usize>>, visited: &mut Vec<bool>) -> bool {
    visited[node] = true;
    for &neighbor in &graph[node] {
        if !visited[neighbor] {
            if dfs(neighbor, Some(node), graph, visited) {
                return true;
            }
        } else if Some(neighbor) != parent {
            return true;
        }
    }
    false
}

This DFS function checks for cycles by visiting nodes and checking if a visited neighbor is not the parent.

Execution Table

Step	Operation	Current Node	Visited Set	Parent Node	Cycle Detected	Visual State
1	Start DFS at node 0	0	{0}	None	No	0(visited)
2	Visit neighbor 1 of node 0	1	{0,1}	0	No	0(visited) -> 1(visited)
3	Visit neighbor 2 of node 1	2	{0,1,2}	1	No	0 -> 1 -> 2(visited)
4	Visit neighbor 1 of node 2	1	{0,1,2}	2	No	0 -> 1 -> 2 (1 visited, parent)
5	Visit neighbor 3 of node 2	3	{0,1,2,3}	2	No	0 -> 1 -> 2 -> 3(visited)
6	Visit neighbor 1 of node 3	1	{0,1,2,3}	3	Yes	Cycle detected at node 3 via neighbor 1
7	Return True up the call stack	3	{0,1,2,3}	2	Yes	Cycle confirmed
8	Return True up the call stack	2	{0,1,2,3}	1	Yes	Cycle confirmed
9	Return True up the call stack	1	{0,1,2,3}	0	Yes	Cycle confirmed
10	Return True at root	0	{0,1,2,3}	None	Yes	Cycle confirmed
11	Stop DFS	-	{0,1,2,3}	-	Yes	Cycle found, traversal ends

💡 Cycle detected at step 6 when visiting neighbor 1 of node 3 which is already visited and not the parent.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
visited	{}	{0}	{0,1}	{0,1,2}	{0,1,2}	{0,1,2,3}	{0,1,2,3}	{0,1,2,3}
current_node	None	0	1	2	2	3	3	Cycle found
parent_node	None	None	0	1	2	2	3	N/A
cycle_detected	False	False	False	False	False	True	True	True

Key Moments - 3 Insights

Why do we check if the visited neighbor is not the parent node?

Because the parent node is the node we came from, so revisiting it does not mean a cycle. See step 4 and 6 in execution_table where neighbor 1 is parent of 2 (no cycle), but neighbor 1 of 3 is visited and not parent (cycle).

What happens if the graph is disconnected?

DFS should be started from every unvisited node to cover all components. The example assumes starting at node 0 covers the connected component. If disconnected, cycle detection must run on each component.

Why do we return true immediately when a cycle is found?

Because once a cycle is detected, no need to continue searching. The recursion unwinds returning true up to the initial call, as shown from step 6 to 10.

Visual Quiz - 3 Questions

Look at the execution_table, what is the visited set after step 3?

A {0,1,2}

B {0,1}

C {0,1,2,3}

D {0}

💡 Hint

Check the Visited Set column at step 3 in execution_table.

At which step does the cycle get detected?

A Step 4

B Step 2

C Step 6

D Step 10

💡 Hint

Look at the Cycle Detected column in execution_table to find when it first becomes Yes.

If the graph had no cycle, what would happen to the cycle_detected variable in variable_tracker?

A It would toggle between True and False

B It would remain False throughout

C It would become True at the end

D It would be True from the start

💡 Hint

Refer to the cycle_detected row in variable_tracker and consider what happens if no cycle is found.

Concept Snapshot

Cycle Detection in Undirected Graph using DFS:
- Start DFS from any node, mark visited
- For each neighbor:
  - If not visited, recurse DFS
  - If visited and not parent, cycle found
- Return true immediately on cycle
- Check all components if graph disconnected

Full Transcript

Cycle detection in an undirected graph uses depth-first search (DFS). We start from any node and mark it visited. For each neighbor, if it is not visited, we recursively visit it. If a neighbor is visited and is not the parent node, a cycle exists. We return true immediately when a cycle is found. If the graph is disconnected, we run DFS from each unvisited node. This method ensures we detect cycles efficiently by tracking visited nodes and parent relationships.

Practice

1. What is the main idea behind detecting a cycle in an undirected graph using DFS?

easy

A. If we visit a node that is already visited and is not the parent, a cycle exists.

B. If all nodes are visited exactly once, the graph has a cycle.

C. If the graph has more edges than nodes, it must have a cycle.

D. If the graph is disconnected, it contains a cycle.

Solution

1. Step 1: Understand DFS traversal in undirected graph

   DFS visits nodes and tracks the parent node to avoid false cycle detection.

2. Step 2: Detect cycle condition

   If a visited node is found that is not the parent, it means a back edge exists, indicating a cycle.

3. Final Answer:

   If we visit a node that is already visited and is not the parent, a cycle exists. -> Option A

4. Quick Check:

   Cycle detection in undirected graph = check visited & parent [OK]

Hint: Check visited nodes excluding parent during DFS to find cycles [OK]

Common Mistakes:

• Ignoring the parent node when checking visited nodes
• Assuming disconnected graph always has cycles
• Confusing cycle detection logic with directed graphs
• Counting edges vs nodes incorrectly

2. Which Rust code snippet correctly initializes an adjacency list for an undirected graph with 3 nodes?

easy

A. let graph = vec![vec![]; 3]; graph[0].push(1); graph[1].push(0); graph[1].push(2); graph[2].push(1);

B. let mut graph = vec![vec![]; 3]; graph[0].push(1); graph[1].push(0); graph[1].push(2); graph[2].push(1);

C. let mut graph = vec![vec![]; 3]; graph[0].push(1); graph[1].push(2); graph[2].push(1);

D. let mut graph = vec![vec![]; 3]; graph[0].push(1); graph[1].push(0); graph[2].push(1);

Solution

1. Step 1: Initialize mutable adjacency list

   Use let mut graph = vec![vec![]; 3]; to create a mutable vector of vectors for 3 nodes.

2. Step 2: Add edges for undirected graph

   For each edge, add both directions: node 0 to 1 and node 1 to 0, node 1 to 2 and node 2 to 1.

3. Final Answer:

   let mut graph = vec![vec![]; 3]; graph[0].push(1); graph[1].push(0); graph[1].push(2); graph[2].push(1); -> Option B

4. Quick Check:

   Mutable adjacency list with bidirectional edges = correct initialization [OK]

Hint: Use 'mut' and push edges both ways for undirected graph [OK]

Common Mistakes:

• Forgetting 'mut' keyword for mutable vector
• Adding edges only one way in undirected graph
• Trying to push to immutable vector
• Incorrect vector initialization syntax

3. What will be the output of the following Rust code snippet detecting cycle in an undirected graph?

fn dfs(node: usize, parent: usize, graph: &Vec, visited: &mut Vec<bool>) -> bool {
    visited[node] = true;
    for &neighbor in &graph[node] {
        if !visited[neighbor] {
            if dfs(neighbor, node, graph, visited) {
                return true;
            }
        } else if neighbor != parent {
            return true;
        }
    }
    false
}

fn main() {
    let mut graph = vec![vec![]; 4];
    graph[0].push(1); graph[1].push(0);
    graph[1].push(2); graph[2].push(1);
    graph[2].push(3); graph[3].push(2);
    graph[3].push(1); graph[1].push(3);

    let mut visited = vec![false; 4];
    let has_cycle = dfs(0, usize::MAX, &graph, &mut visited);
    println!("{}", has_cycle);
}

medium

A. Runtime panic

B. false

C. true

D. Compilation error

Solution

1. Step 1: Analyze graph edges and structure

   The graph edges form a cycle: 1-2-3-1, so cycle exists.

2. Step 2: Trace DFS cycle detection logic

   DFS visits nodes and finds a visited neighbor (1) not equal to parent, returning true.

3. Final Answer:

   true -> Option C

4. Quick Check:

   Cycle detected in DFS = true [OK]

Hint: Look for back edges to visited nodes excluding parent [OK]

Common Mistakes:

• Ignoring the edge from 3 to 1 forming a cycle
• Confusing parent node with visited node
• Assuming no cycle if start node is 0
• Misreading DFS return conditions

4. Identify the bug in this Rust DFS cycle detection code for an undirected graph:

fn dfs(node: usize, parent: usize, graph: &Vec, visited: &mut Vec<bool>) -> bool {
    visited[node] = true;
    for &neighbor in &graph[node] {
        if visited[neighbor] {
            if neighbor != parent {
                return true;
            }
        } else {
            dfs(neighbor, node, graph, visited);
        }
    }
    false
}

medium

A. Missing return statement for recursive dfs call

B. Incorrect parent check condition

C. Visited vector should be immutable

D. Graph should be mutable

Solution

1. Step 1: Check recursive call usage

   The recursive call to dfs is made but its result is ignored, missing return propagation.

2. Step 2: Fix by returning recursive call result

   Return the result of dfs(neighbor, node, graph, visited) to propagate cycle detection upwards.

3. Final Answer:

   Missing return statement for recursive dfs call -> Option A

4. Quick Check:

   Return recursive dfs result to detect cycles correctly [OK]

Hint: Always return recursive call result in DFS for cycle detection [OK]

Common Mistakes:

• Ignoring return value of recursive DFS calls
• Confusing parent check logic
• Using immutable visited vector incorrectly
• Assuming graph mutability is required here

5. Given an undirected graph represented as adjacency list in Rust, how can you modify the DFS cycle detection to handle disconnected graphs and detect cycles in all components? Choose the best approach.

hard

A. Use BFS instead of DFS for cycle detection.

B. Run DFS only from node 0, assuming graph is connected.

C. Mark all nodes visited initially and then run DFS once.

D. Run DFS from every unvisited node in a loop to cover all components.

Solution

1. Step 1: Understand disconnected graph scenario

   Disconnected graphs have multiple components; DFS from one node covers only one component.

2. Step 2: Modify DFS to run on all components

   Loop over all nodes, run DFS if node is unvisited to detect cycles in every component.

3. Final Answer:

   Run DFS from every unvisited node in a loop to cover all components. -> Option D

4. Quick Check:

   Cycle detection in disconnected graph = DFS from all unvisited nodes [OK]

Hint: Loop DFS over all nodes to cover disconnected components [OK]

Common Mistakes:

• Assuming graph is always connected
• Running DFS only once from node 0
• Using BFS without cycle detection logic
• Marking all nodes visited before DFS