DFS Depth First Search on Graph in DSA Rust - Execution Trace

Concept Flow - DFS Depth First Search on Graph

Start at source node

↓

Mark node as visited

↓

For each neighbor

↓

If neighbor not visited?

No→Skip

Yes↓

Recursively DFS on neighbor

↓

All neighbors visited?

↓

Backtrack to previous node

↓

Done when all reachable nodes visited

Start from a node, visit it, then recursively visit all its unvisited neighbors, backtracking when no unvisited neighbors remain.

Execution Sample

DSA Rust

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

This code visits nodes in a graph using DFS, marking nodes visited and recursively exploring neighbors.

Execution Table

Step	Operation	Current Node	Visited Set	Stack (Call Trace)	Action	Graph State
1	Start DFS	0	[0]	[0]	Visit node 0	0: [1, 2], 1: [0, 3], 2: [0, 4], 3: [1], 4: [2]
2	Explore neighbor	0	[0]	[0]	Check neighbor 1	Same
3	Recurse DFS	1	[0,1]	[0,1]	Visit node 1	Same
4	Explore neighbor	1	[0,1]	[0,1]	Check neighbor 0 (visited)	Same
5	Skip neighbor	1	[0,1]	[0,1]	Neighbor 0 already visited, skip	Same
6	Explore neighbor	1	[0,1]	[0,1]	Check neighbor 3	Same
7	Recurse DFS	3	[0,1,3]	[0,1,3]	Visit node 3	Same
8	Explore neighbor	3	[0,1,3]	[0,1,3]	Check neighbor 1 (visited)	Same
9	Skip neighbor	3	[0,1,3]	[0,1,3]	Neighbor 1 already visited, skip	Same
10	Backtrack	3	[0,1,3]	[0,1]	All neighbors visited, backtrack	Same
11	Back to node 1	1	[0,1,3]	[0,1]	Continue neighbors	Same
12	All neighbors visited	1	[0,1,3]	[0]	Backtrack to node 0	Same
13	Back to node 0	0	[0,1,3]	[0]	Continue neighbors	Same
14	Explore neighbor	0	[0,1,3]	[0]	Check neighbor 2	Same
15	Recurse DFS	2	[0,1,2,3]	[0,2]	Visit node 2	Same
16	Explore neighbor	2	[0,1,2,3]	[0,2]	Check neighbor 0 (visited)	Same
17	Skip neighbor	2	[0,1,2,3]	[0,2]	Neighbor 0 already visited, skip	Same
18	Explore neighbor	2	[0,1,2,3]	[0,2]	Check neighbor 4	Same
19	Recurse DFS	4	[0,1,2,3,4]	[0,2,4]	Visit node 4	Same
20	Explore neighbor	4	[0,1,2,3,4]	[0,2,4]	Check neighbor 2 (visited)	Same
21	Skip neighbor	4	[0,1,2,3,4]	[0,2,4]	Neighbor 2 already visited, skip	Same
22	Backtrack	4	[0,1,2,3,4]	[0,2]	All neighbors visited, backtrack	Same
23	Back to node 2	2	[0,1,2,3,4]	[0,2]	All neighbors visited, backtrack	Same
24	Back to node 0	0	[0,1,2,3,4]	[0]	All neighbors visited, backtrack	Same
25	DFS Complete	-	[0,1,2,3,4]	[]	All reachable nodes visited	Same

💡 All nodes reachable from node 0 are visited; DFS ends.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 7	After Step 19	Final
visited	[false, false, false, false, false]	[true, false, false, false, false]	[true, true, false, false, false]	[true, true, false, true, false]	[true, true, true, true, true]	[true, true, true, true, true]
stack (call trace)	[]	[0]	[0,1]	[0,1,3]	[0,2,4]	[]
current_node	None	0	1	3	4	None

Key Moments - 3 Insights

Why do we mark a node as visited before exploring neighbors?

Marking a node visited immediately (see Step 1) prevents revisiting it later, avoiding infinite loops in cycles (see Steps 4 and 6 where neighbors already visited are skipped).

Why do we backtrack after all neighbors are visited?

Backtracking (see Steps 10, 12, 22, 23, 24) happens when no unvisited neighbors remain, allowing DFS to explore other branches from previous nodes.

How does the call stack represent the traversal path?

The stack (call trace) shows nodes currently being explored (see variable_tracker and Steps 1, 3, 7, 19). It grows when recursing deeper and shrinks when backtracking.

Visual Quiz - 3 Questions

Look at the execution_table at Step 7, which node is currently being visited?

A Node 1

B Node 3

C Node 0

D Node 2

💡 Hint

Check the 'Current Node' column at Step 7 in the execution_table.

At which step does the DFS first backtrack from node 3?

A Step 11

B Step 9

C Step 10

D Step 12

💡 Hint

Look for 'Backtrack' operation with current node 3 in the execution_table.

According to variable_tracker, what is the state of 'visited' after Step 19?

A [true, true, true, true, true]

B [false, true, true, true, true]

C [true, true, false, true, true]

D [true, false, true, true, true]

💡 Hint

Check the 'visited' row in variable_tracker after Step 19.

Concept Snapshot

DFS (Depth First Search) explores graph nodes by going deep first.
Start at a node, mark visited, recursively visit unvisited neighbors.
Use a call stack (implicit via recursion) to track path.
Backtrack when no unvisited neighbors remain.
Prevents cycles by marking nodes visited immediately.
Useful for connectivity, path finding, and graph traversal.

Full Transcript

DFS Depth First Search starts at a chosen node, marks it visited, then explores each neighbor recursively if not visited. The process uses a call stack to remember the path. When a node has no unvisited neighbors, DFS backtracks to explore other branches. This prevents infinite loops in graphs with cycles by marking nodes as visited immediately upon first visit. The execution trace shows visiting nodes 0, 1, 3, backtracking, then visiting 2, 4, and completing when all reachable nodes are visited.

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