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

Cycle Detection in Undirected Graph

📖 Scenario: You are working with a simple map of connected places. Each place is connected to others by roads. You want to check if there is any loop in the roads, so you don't get stuck driving in circles.

🎯 Goal: Build a program that detects if there is a cycle (loop) in an undirected graph using Rust. You will create the graph, set up a helper structure, write the cycle detection logic, and finally print if a cycle exists.

📋 What You'll Learn

Create an undirected graph using an adjacency list representation with exact edges

Create a visited vector to track visited nodes

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

Print whether the graph contains a cycle or not

💡 Why This Matters

🌍 Real World

Cycle detection helps in network design, avoiding loops in road maps, and detecting deadlocks in systems.

💼 Career

Understanding graph traversal and cycle detection is important for software engineers working on networking, databases, and system design.

1

Create the graph as an adjacency list

Create a variable called graph as a Vec> with 5 nodes (0 to 4). Add these edges exactly: 0-1, 1-2, 2-3, 3-4, and 4-1. Since the graph is undirected, add each edge in both directions.

DSA Rust

# Your code here

Hint

Think of graph as a list where each index is a place, and inside each index is a list of connected places.

2

Create a visited vector to track nodes

Add a variable called visited as a Vec with 5 elements, all set to false. This will help track which nodes have been checked.

DSA Rust

fn main() {
    let mut graph: Vec> = vec![vec![], vec![], vec![], vec![], vec![]];
    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(4);
    graph[4].push(3);
    graph[4].push(1);
    graph[1].push(4);

    // Create visited vector
    // Your code here
}

Hint

Use vec![false; 5] to create a list of 5 false values.

3

Write the DFS function to detect cycles

Add a function called dfs that takes node: usize, parent: Option, graph: &Vec>, and visited: &mut Vec. It returns bool. The function should mark node as visited, then check all neighbors. If a neighbor is not visited, call dfs recursively. If a neighbor is visited and is not the parent, return true indicating a cycle. Return false if no cycle found.

DSA Rust

fn main() {
    let mut graph: Vec> = vec![vec![], vec![], vec![], vec![], vec![]];
    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(4);
    graph[4].push(3);
    graph[4].push(1);
    graph[1].push(4);

    let mut visited: Vec = vec![false; 5];

    // Add dfs function here
    // Your code here
}

Hint

Use recursion to visit neighbors. If you find a visited neighbor that is not the parent, a cycle exists.

4

Check for cycle and print the result

Use a for loop with variable node from 0 to 4. If visited[node] is false, call dfs(node, None, &graph, &mut visited). If it returns true, print exactly "Cycle detected" and stop. If no cycle is found after the loop, print exactly "No cycle detected".

DSA Rust

fn main() {
    let mut graph: Vec> = vec![vec![], vec![], vec![], vec![], vec![]];
    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(4);
    graph[4].push(3);
    graph[4].push(1);
    graph[1].push(4);

    let mut visited: Vec = vec![false; 5];

    fn dfs(node: usize, parent: Option, graph: &Vec>, visited: &mut Vec) -> 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
    }

    // Check for cycle and print result
    // Your code here
}

Hint

Loop through all nodes. If a node is not visited, run dfs. Print "Cycle detected" if found, else "No cycle detected".

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