Cycle Detection in Undirected Graph in DSA Rust

Mental Model

We want to find if there is a loop in the graph by checking if we revisit a node through a different path.

Analogy: Imagine walking paths in a park where some paths connect back to where you started. If you can return to the same spot without retracing your exact steps, there is a cycle.

0 -> 1 -> 2
↑         ↓
4 ← 3 ←---

Dry Run Walkthrough

Input: Graph with edges: 0-1, 1-2, 2-3, 3-4, 4-0 (forms a cycle)

Goal: Detect if the graph contains any cycle

Step 1: Start DFS from node 0, mark 0 visited

Visited: {0}
Stack: [0]

Why: We begin exploring from node 0 to find cycles

Step 2: Move to neighbor 1, mark 1 visited

Visited: {0,1}
Stack: [0,1]

Why: Explore neighbors to find a cycle

Step 3: Move to neighbor 2, mark 2 visited

Visited: {0,1,2}
Stack: [0,1,2]

Why: Continue deeper to check for cycles

Step 4: Move to neighbor 3, mark 3 visited

Visited: {0,1,2,3}
Stack: [0,1,2,3]

Why: Keep exploring neighbors

Step 5: Move to neighbor 4, mark 4 visited

Visited: {0,1,2,3,4}
Stack: [0,1,2,3,4]

Why: Reached last node in path

Step 6: Check neighbors of 4: neighbor 0 is visited and not parent, cycle detected

Cycle found at node 4 via neighbor 0

Why: Visiting a visited node that is not the parent means a cycle

Result:

Cycle detected in the graph

Annotated Code

DSA Rust

use std::collections::HashSet;

struct Graph {
    adj_list: Vec<Vec<usize>>,
}

impl Graph {
    fn new(n: usize) -> Self {
        Self { adj_list: vec![vec![]; n] }
    }

    fn add_edge(&mut self, u: usize, v: usize) {
        self.adj_list[u].push(v);
        self.adj_list[v].push(u);
    }

    fn dfs(&self, node: usize, parent: Option<usize>, visited: &mut HashSet<usize>) -> bool {
        visited.insert(node); // mark current node visited
        for &neighbor in &self.adj_list[node] {
            if !visited.contains(&neighbor) {
                if self.dfs(neighbor, Some(node), visited) {
                    return true; // cycle found deeper
                }
            } else if Some(neighbor) != parent {
                return true; // cycle found: visited neighbor not parent
            }
        }
        false // no cycle found from this path
    }

    fn has_cycle(&self) -> bool {
        let mut visited = HashSet::new();
        for node in 0..self.adj_list.len() {
            if !visited.contains(&node) {
                if self.dfs(node, None, &mut visited) {
                    return true; // cycle detected
                }
            }
        }
        false // no cycle in any component
    }
}

fn main() {
    let mut graph = Graph::new(5);
    graph.add_edge(0, 1);
    graph.add_edge(1, 2);
    graph.add_edge(2, 3);
    graph.add_edge(3, 4);
    graph.add_edge(4, 0); // creates a cycle

    if graph.has_cycle() {
        println!("Cycle detected in the graph");
    } else {
        println!("No cycle detected");
    }
}

visited.insert(node); // mark current node visited

mark node as visited to avoid revisiting

if !visited.contains(&neighbor) {

explore unvisited neighbors recursively

if self.dfs(neighbor, Some(node), visited) { return true; }

if cycle found deeper, propagate true up

else if Some(neighbor) != parent { return true; }

detect cycle if visited neighbor is not parent

for node in 0..self.adj_list.len() { if !visited.contains(&node) { if self.dfs(node, None, &mut visited) { return true; } } }

check all graph components for cycles

Output

Cycle detected in the graph

Complexity Analysis

Time: O(V + E) because we visit each vertex and edge once during DFS

Space: O(V) for the visited set and recursion stack in worst case

vs Alternative: Compared to using union-find which also runs in near O(V + E), DFS is simpler to implement and understand for cycle detection in undirected graphs

Edge Cases

Empty graph with no nodes

No cycle detected because there are no edges

DSA Rust

for node in 0..self.adj_list.len() { if !visited.contains(&node) {

Graph with a single node and no edges

No cycle detected because no edges exist

DSA Rust

for node in 0..self.adj_list.len() { if !visited.contains(&node) {

Graph with multiple disconnected components

Each component is checked separately for cycles

DSA Rust

for node in 0..self.adj_list.len() { if !visited.contains(&node) {

When to Use This Pattern

When you see a problem asking if an undirected graph contains loops, reach for DFS with parent tracking to detect cycles efficiently.

Common Mistakes

Mistake: Treating visited neighbor as cycle even if it is the parent node
Fix: Check that the visited neighbor is not the parent before declaring a cycle

Summary

Detects if an undirected graph contains any cycle by DFS traversal with parent tracking.

Use when you need to find loops in undirected graphs to avoid infinite traversals or validate graph structure.

The key insight is that revisiting a visited node that is not the parent means a cycle exists.

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