DFS Depth First Search on Graph in DSA Rust - Deep Dive

Overview - DFS Depth First Search on Graph

What is it?

Depth First Search (DFS) is a way to explore all the points (nodes) in a graph by going as deep as possible along each path before backtracking. Imagine starting at one node and visiting neighbors one by one, going deeper until no new nodes are left to visit. It helps find paths, check connections, and explore structures in graphs.

Why it matters

Without DFS, exploring complex networks like social connections, maps, or web links would be slow and confusing. DFS helps computers quickly find routes, detect cycles, or check if everything is connected. It is a foundation for many algorithms in navigation, puzzle solving, and network analysis.

Where it fits

Before learning DFS, you should understand what graphs are and how they represent connections. After DFS, you can learn other graph searches like Breadth First Search (BFS), shortest path algorithms, and graph traversal optimizations.

Mental Model

Core Idea

DFS explores a graph by going as far as possible down one path before stepping back to explore others.

Think of it like...

DFS is like exploring a maze by always taking the first unexplored path you find, going deep until you hit a dead end, then backtracking to try other paths.

Graph example:

  A
 / \
B   C
|   |
D - E

DFS starting at A:
A -> B -> D -> E -> C

Traversal path:
A
│
├─> B
│   │
│   └─> D
│       └─> E
└─> C

Build-Up - 7 Steps

1

Foundation

Understanding Graphs and Nodes

Concept: Introduce what a graph is and how nodes connect with edges.

A graph is a collection of points called nodes connected by lines called edges. Nodes can represent anything like cities or people, and edges show relationships or paths between them. Graphs can be directed (one-way) or undirected (two-way).

Result

You can visualize and represent connections between objects as nodes and edges.

Understanding the structure of graphs is essential because DFS works by moving through these connections step-by-step.

2

Foundation

Representing Graphs in Code

Concept: Learn how to store graphs in a program using adjacency lists.

An adjacency list stores each node with a list of its neighbors. For example, node A's list contains nodes B and C if A connects to B and C. This is memory efficient and easy to use for traversal.

Result

You can create a graph in code that DFS can explore.

Choosing the right graph representation makes traversal algorithms like DFS simpler and faster.

3

Intermediate

Implementing DFS Recursively

🤔Before reading on: Do you think DFS visits nodes in the order they appear in the adjacency list or in some other order? Commit to your answer.

Concept: Use recursion to explore nodes deeply, visiting neighbors one by one.

Start at a node, mark it visited, then call DFS on each unvisited neighbor recursively. This continues until all reachable nodes are visited. Use a visited set to avoid revisiting nodes and infinite loops.

Result

DFS visits nodes deeply, exploring one path fully before backtracking.

Recursion naturally fits DFS because it remembers the path taken and backtracks automatically when no new nodes remain.

4

Intermediate

Handling Cycles and Visited Nodes

🤔Before reading on: What happens if DFS does not track visited nodes in a graph with cycles? Commit to your answer.

Concept: Prevent infinite loops by tracking which nodes have been visited.

Graphs can have cycles where nodes connect back to earlier nodes. Without marking visited nodes, DFS would loop forever. Use a boolean visited array or set to skip nodes already explored.

Result

DFS safely explores graphs with cycles without repeating nodes endlessly.

Tracking visited nodes is critical to avoid infinite loops and ensure DFS completes.

5

Intermediate

Iterative DFS Using a Stack

🤔Before reading on: Do you think DFS can be done without recursion? Commit to your answer.

Concept: Use a stack data structure to simulate recursion and control the order of node visits.

Instead of recursion, use a stack to store nodes to visit. Pop a node, visit it, then push its unvisited neighbors onto the stack. This mimics the call stack of recursion and allows DFS without function calls.

Result

DFS can be implemented iteratively, useful in languages or situations where recursion is limited.

Knowing iterative DFS expands your toolkit and helps avoid stack overflow in deep graphs.

6

Advanced

DFS Applications: Cycle Detection and Connectivity

🤔Before reading on: Can DFS alone detect if a graph has cycles? Commit to your answer.

Concept: Use DFS to find cycles and check if all nodes are connected.

By tracking recursion stack or parent nodes during DFS, you can detect cycles. Also, if DFS visits all nodes from one start node, the graph is connected. These checks are fundamental in graph algorithms.

Result

DFS helps solve real problems like cycle detection and connectivity verification.

Applying DFS beyond traversal shows its power in solving complex graph problems.

7

Expert

Optimizing DFS with Early Stopping and Ordering

🤔Before reading on: Does the order of neighbors visited affect DFS results? Commit to your answer.

Concept: Improve DFS by stopping early when a target is found and ordering neighbors for efficiency.

In some problems, you can stop DFS once you find the goal, saving time. Also, sorting neighbors or prioritizing certain edges can lead to faster solutions or specific traversal orders. These tweaks require careful design.

Result

Optimized DFS can be faster and more targeted in large graphs.

Understanding how traversal order and early stopping affect DFS results is key for performance tuning in real systems.

Under the Hood

DFS uses a stack structure, either implicitly via recursion or explicitly, to keep track of nodes to visit. It marks nodes as visited to avoid revisiting and infinite loops. The algorithm explores as deep as possible along each branch before backtracking, ensuring all reachable nodes are visited.

Why designed this way?

DFS was designed to explore graphs deeply and systematically, which is useful for problems like pathfinding and cycle detection. Using recursion or a stack matches the natural depth-first exploration pattern. Alternatives like BFS explore breadth-wise but are less suited for deep path exploration.

Start
  │
  ▼
[Current Node]
  │
  ├─> Mark visited
  │
  ├─> For each neighbor:
  │       ├─> If not visited:
  │       │       └─> Push neighbor (stack or recursion)
  │       └─> Else skip
  │
  ▼
Backtrack when no neighbors left
  │
  ▼
Repeat until stack empty or recursion ends

Myth Busters - 4 Common Misconceptions

Quick: Does DFS always find the shortest path between two nodes? Commit to yes or no.

Common Belief: DFS always finds the shortest path between nodes.

Reality: DFS does not guarantee the shortest path; it explores deeply and may find longer paths first.

Why it matters: Using DFS for shortest path can lead to incorrect or inefficient results; algorithms like BFS or Dijkstra are better suited.

Quick: Can DFS be used on graphs with cycles without any special handling? Commit to yes or no.

Common Belief: DFS works fine on any graph without tracking visited nodes.

Reality: Without tracking visited nodes, DFS can get stuck in infinite loops on cyclic graphs.

Why it matters: Failing to track visited nodes causes programs to hang or crash, making DFS unusable on real-world graphs.

Quick: Is recursive DFS always better than iterative DFS? Commit to yes or no.

Common Belief: Recursive DFS is always simpler and better than iterative DFS.

Reality: Recursive DFS can cause stack overflow on large graphs; iterative DFS avoids this by using an explicit stack.

Why it matters: Choosing recursive DFS blindly can cause crashes in production; knowing iterative DFS is essential for robustness.

Quick: Does the order of neighbors in the adjacency list never affect DFS traversal? Commit to yes or no.

Common Belief: The order of neighbors does not affect DFS traversal order or results.

Reality: Neighbor order affects the path DFS takes and the order nodes are visited, which can change outcomes in some algorithms.

Why it matters: Ignoring neighbor order can cause subtle bugs or unexpected results in graph algorithms relying on DFS.

Expert Zone

1

DFS traversal order can be controlled by sorting neighbors, which is crucial in lexicographically smallest path problems.

2

Using a recursion stack or parent tracking during DFS enables detection of back edges, which identify cycles in directed graphs.

3

In some graphs, iterative DFS with manual stack management can be optimized to reduce memory overhead by reusing data structures.

When NOT to use

DFS is not suitable when shortest paths are needed; use BFS or Dijkstra instead. For very large or infinite graphs, iterative deepening DFS or heuristic searches like A* are better. Also, DFS is less effective on graphs where breadth exploration is required.

Production Patterns

DFS is used in compilers for syntax checking, in network analysis to find connected components, and in puzzle solvers like mazes. It is also a building block for algorithms like topological sorting and strongly connected components detection.

Connections

Breadth First Search (BFS)

BFS explores graphs level by level, opposite to DFS's deep exploration.

Understanding DFS helps grasp BFS as a complementary approach, highlighting different traversal strategies for different problems.

Backtracking Algorithms

DFS underpins backtracking by exploring choices deeply and undoing them when needed.

Knowing DFS clarifies how backtracking systematically searches solution spaces in puzzles and optimization.

Human Problem Solving

DFS mirrors how people explore options deeply before reconsidering alternatives.

Recognizing DFS in human thinking patterns helps design algorithms that mimic natural exploration and decision-making.

Common Pitfalls

#1 Not marking nodes as visited causes infinite loops in cyclic graphs.

Wrong approach:

fn dfs(node: usize, graph: &Vec>) {
println!("Visiting {}", node);
for &neighbor in &graph[node] {
dfs(neighbor, graph);
}
}

Correct approach:

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

Root cause:

Forgetting to track visited nodes ignores cycles, causing endless recursion.

#2 Using recursion without limits on large graphs causes stack overflow.

Wrong approach:

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

Correct approach:

fn dfs_iterative(start: usize, graph: &Vec>) {
let mut visited = vec![false; graph.len()];
let mut stack = vec![start];
while let Some(node) = stack.pop() {
if !visited[node] {
visited[node] = true;
println!("Visiting {}", node);
for &neighbor in &graph[node] {
if !visited[neighbor] {
stack.push(neighbor);
}
}
}
}
}

Root cause:

Recursion depth exceeds system limits; iterative approach avoids this.

#3 Assuming DFS finds shortest paths leads to wrong results.

Wrong approach:

fn dfs_find_path(start: usize, target: usize, graph: &Vec>, visited: &mut Vec) -> bool {
if start == target { return true; }
visited[start] = true;
for &neighbor in &graph[start] {
if !visited[neighbor] && dfs_find_path(neighbor, target, graph, visited) {
return true;
}
}
false
}
// Using this to find shortest path incorrectly

Correct approach:

fn bfs_shortest_path(start: usize, target: usize, graph: &Vec>) -> Option {
let mut visited = vec![false; graph.len()];
let mut queue = std::collections::VecDeque::new();
let mut distance = vec![0; graph.len()];
visited[start] = true;
queue.push_back(start);
while let Some(node) = queue.pop_front() {
if node == target { return Some(distance[node]); }
for &neighbor in &graph[node] {
if !visited[neighbor] {
visited[neighbor] = true;
distance[neighbor] = distance[node] + 1;
queue.push_back(neighbor);
}
}
}
None
}

Root cause:

Confusing DFS traversal with shortest path algorithms.

Key Takeaways

DFS explores graphs by going deep along each path before backtracking, using recursion or a stack.

Tracking visited nodes is essential to avoid infinite loops in graphs with cycles.

DFS does not guarantee shortest paths; use BFS or other algorithms for that purpose.

Iterative DFS is important to handle large graphs without risking stack overflow.

DFS is a foundation for many graph algorithms like cycle detection, connectivity checks, and backtracking.

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