DFS Depth First Search on Graph in DSA Rust

Mental Model

DFS explores as far as possible along each branch before backtracking. It visits nodes by going deep first.

Analogy: Imagine exploring a maze by always taking the first unexplored path you find until you hit a dead end, then backtracking to try other paths.

Graph adjacency list:
0 -> [1, 2]
1 -> [2]
2 -> [0, 3]
3 -> []
Start at node 2 ↑

Dry Run Walkthrough

Input: Graph with edges: 0->1, 0->2, 1->2, 2->0, 2->3, start DFS at node 2

Goal: Visit all nodes reachable from node 2 using DFS order

Step 1: Start DFS at node 2, mark 2 visited

Visited: {2}
Stack: [2]

Why: We begin from node 2 to explore its neighbors

Step 2: From 2, go to neighbor 0, mark 0 visited

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

Why: DFS goes deep by visiting first unvisited neighbor

Step 3: From 0, go to neighbor 1, mark 1 visited

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

Why: Continue deep traversal to next unvisited neighbor

Step 4: From 1, neighbor 2 already visited, backtrack

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

Why: No new nodes from 1, so backtrack to 0

Step 5: From 0, next neighbor 2 already visited, backtrack

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

Why: All neighbors of 0 visited, backtrack to 2

Step 6: From 2, next neighbor 3, mark 3 visited

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

Why: Visit remaining unvisited neighbor of 2

Step 7: From 3, no neighbors, backtrack

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

Why: Dead end reached, backtrack to 2

Step 8: All neighbors of 2 visited, DFS complete

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

Why: No more nodes to visit, traversal ends

Result:

Visited nodes in DFS order: 2 -> 0 -> 1 -> 3

Annotated Code

DSA Rust

use std::collections::HashSet;

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

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

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

    fn dfs(&self, start: usize) -> Vec<usize> {
        let mut visited = HashSet::new();
        let mut result = Vec::new();
        self.dfs_helper(start, &mut visited, &mut result);
        result
    }

    fn dfs_helper(&self, node: usize, visited: &mut HashSet<usize>, result: &mut Vec<usize>) {
        if visited.contains(&node) {
            return; // already visited
        }
        visited.insert(node); // mark node visited
        result.push(node); // record visit order
        for &neighbor in &self.adj_list[node] {
            self.dfs_helper(neighbor, visited, result); // visit neighbors recursively
        }
    }
}

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

    let dfs_order = graph.dfs(2);
    for node in dfs_order {
        print!("{} -> ", node);
    }
    print!("null\n");
}

if visited.contains(&node) { return; }

skip nodes already visited to avoid cycles

visited.insert(node);

mark current node as visited

result.push(node);

record node visit order

for &neighbor in &self.adj_list[node] { self.dfs_helper(neighbor, visited, result); }

recursively visit all neighbors deeply

Output

2 -> 0 -> 1 -> 3 -> null

Complexity Analysis

Time: O(V + E) because DFS visits every vertex and edge once

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

vs Alternative: Compared to BFS which uses a queue and visits nodes level by level, DFS uses recursion or stack to go deep first; both have similar time but different traversal order

Edge Cases

Empty graph with no nodes

DFS returns empty visit order without error

DSA Rust

if visited.contains(&node) { return; }

Graph with single node and no edges

DFS visits the single node and stops

DSA Rust

visited.insert(node);

Graph with cycles

DFS avoids infinite loops by checking visited nodes

DSA Rust

if visited.contains(&node) { return; }

When to Use This Pattern

When a problem asks to explore all connected parts of a graph deeply or find paths, use DFS because it explores one branch fully before moving to another.

Common Mistakes

Mistake: Not marking nodes as visited before recursive calls causing infinite loops
Fix: Insert the node into visited set before recursing on neighbors

Mistake: Visiting neighbors in wrong order causing unexpected traversal
Fix: Follow adjacency list order consistently for predictable DFS order

Summary

DFS visits graph nodes by going deep along each path before backtracking.

Use DFS when you want to explore all nodes reachable from a start node deeply or find paths.

The key insight is to mark nodes visited before recursion to avoid cycles and infinite loops.

Practice

1. What is the main idea behind Depth First Search (DFS) on a graph?

easy

A. Explore as far as possible along each branch before backtracking

B. Visit all nodes at the current depth before moving deeper

C. Visit nodes randomly without any order

D. Only visit nodes with the highest value first

Solution

1. Step 1: Understand DFS traversal

   DFS explores a graph by going deep into one branch before exploring others.

2. Step 2: Compare with other traversal methods

   BFS visits nodes level by level, but DFS goes deep first.

3. Final Answer:

   Explore as far as possible along each branch before backtracking -> Option A

4. Quick Check:

   DFS = deep exploration first [OK]

Hint: DFS means go deep first, then backtrack [OK]

Common Mistakes:

• Confusing DFS with BFS
• Thinking DFS visits nodes level-wise
• Assuming DFS visits nodes randomly

2. Which of the following is the correct Rust function signature for a recursive DFS function on a graph represented as adjacency list?

easy

A. fn dfs(graph: &mut Vec, node: usize, visited: Vec<bool>)

B. fn dfs(graph: Vec, node: usize, visited: Vec<bool>)

C. fn dfs(graph: &Vec, node: usize, visited: &mut Vec<bool>)

D. fn dfs(graph: Vec, node: usize, visited: &mut Vec<bool>)

Solution

1. Step 1: Understand parameter passing in Rust for DFS

   The graph should be passed by reference to avoid copying, and visited vector should be mutable reference to mark nodes visited.

2. Step 2: Check each option

   fn dfs(graph: &Vec, node: usize, visited: &mut Vec<bool>) passes graph by reference and visited as mutable reference, which is correct for DFS recursion.

3. Final Answer:

   fn dfs(graph: &Vec, node: usize, visited: &mut Vec<bool>) -> Option C

4. Quick Check:

   Graph by ref + visited mutable ref = correct DFS signature [OK]

Hint: Pass graph by ref and visited as mutable ref [OK]

Common Mistakes:

• Passing graph or visited by value causing copies
• Not using mutable reference for visited
• Using mutable reference for graph unnecessarily

3. What is the output of the following Rust DFS traversal starting from node 0?

fn dfs(graph: &Vec, node: usize, visited: &mut Vec<bool>, result: &mut Vec<usize>) {
    visited[node] = true;
    result.push(node);
    for &neighbor in &graph[node] {
        if !visited[neighbor] {
            dfs(graph, neighbor, visited, result);
        }
    }
}

fn main() {
    let graph = vec![
        vec![1, 2],
        vec![0, 3],
        vec![0],
        vec![1]
    ];
    let mut visited = vec![false; 4];
    let mut result = Vec::new();
    dfs(&graph, 0, &mut visited, &mut result);
    println!("{:?}", result);
}

medium

A. [0, 2, 1, 3]

B. [0, 1, 3, 2]

C. [0, 1, 2, 3]

D. [1, 0, 2, 3]

Solution

1. Step 1: Trace DFS starting at node 0

   Start at 0, mark visited, add 0. Neighbors: 1, 2. Visit 1 first.

2. Step 2: Continue DFS from node 1

   Visit 1, add 1. Neighbors: 0 (visited), 3 (not visited). Visit 3 next.

3. Step 3: Visit node 3

   Visit 3, add 3. Neighbor: 1 (visited). Backtrack to 0 and visit 2.

4. Step 4: Visit node 2

   Visit 2, add 2. Neighbor: 0 (visited). DFS complete.

5. Final Answer:

   [0, 1, 3, 2] -> Option B

6. Quick Check:

   DFS order from 0 = [0,1,3,2] [OK]

Hint: Follow neighbors in order, mark visited, backtrack [OK]

Common Mistakes:

• Visiting neighbors out of order
• Not marking visited nodes
• Confusing BFS order with DFS

4. Identify the bug in this DFS Rust code snippet and choose the fix:

fn dfs(graph: &Vec, node: usize, visited: &mut Vec<bool>) {
    visited[node] = true;
    for neighbor in &graph[node] {
        if visited[*neighbor] {
            dfs(graph, *neighbor, visited);
        }
    }
}

medium

A. Change if visited[*neighbor] to if !visited[*neighbor]

B. Change visited[node] = true to visited[node] = false

C. Remove the for loop and call dfs only once

D. Change neighbor to node inside the loop

Solution

1. Step 1: Analyze the condition for recursive DFS call

   The code calls dfs only if visited[*neighbor] is true, meaning already visited nodes are revisited, causing infinite recursion.

2. Step 2: Correct the condition to avoid revisiting

   Change condition to if !visited[*neighbor] to visit only unvisited neighbors.

3. Final Answer:

   Change if visited[*neighbor] to if !visited[*neighbor] -> Option A

4. Quick Check:

   Visit unvisited neighbors only [OK]

Hint: Call DFS only on unvisited neighbors [OK]

Common Mistakes:

• Calling DFS on visited nodes causing infinite loops
• Incorrectly marking nodes as unvisited
• Removing necessary loops

5. Given a graph with possible cycles, how can you modify DFS in Rust to detect if the graph contains a cycle?

hard

A. Use BFS instead of DFS to detect cycles

B. Only mark nodes visited after all neighbors are visited

C. Ignore visited nodes and continue traversal

D. Use a recursion stack (call stack) boolean vector to track nodes in the current path and detect back edges

Solution

1. Step 1: Understand cycle detection in DFS

   To detect cycles, track nodes currently in recursion stack to find back edges indicating cycles.

2. Step 2: Implement recursion stack tracking

   Use a boolean vector to mark nodes in current DFS path; if a neighbor is in this stack, a cycle exists.

3. Step 3: Other options are incorrect

   Marking visited after neighbors or using BFS won't detect cycles reliably; ignoring visited nodes causes infinite loops.

4. Final Answer:

   Use a recursion stack (call stack) boolean vector to track nodes in the current path and detect back edges -> Option D

5. Quick Check:

   Recursion stack tracks cycles in DFS [OK]

Hint: Track recursion stack to find cycles in DFS [OK]

Common Mistakes:

• Not tracking recursion stack causing missed cycles
• Using BFS which needs extra logic for cycles
• Ignoring visited nodes causing infinite loops