Depth-First Search (DFS)

Depth-first search (DFS) is a graph traversal algorithm that explores a graph by going as deep as possible along each branch before backtracking. Starting from a source vertex, DFS follows one path until it can no longer continue, then returns to explore alternative paths.

DFS is commonly used for tasks such as cycle detection, topological sorting, and exploring connected components.

DFS Idea

The core idea behind DFS is:

1. Start from a given source vertex
2. Visit a vertex and mark it as visited
3. Recursively visit one unvisited neighbor at a time
4. Backtrack when no further progress is possible

DFS can be implemented using recursion or an explicit stack.

Example Graph

A --- B --- D
|     |
C     E

Starting DFS from vertex A (one possible order):

A → B → D → E → C

DFS order is not unique and depends on neighbor ordering.

DFS Algorithm Steps

1. Mark the starting vertex as visited

2. Visit the vertex

3. For each unvisited neighbor:

   • Recursively apply DFS

DFS Using Adjacency List

DFS is naturally expressed using recursion and works efficiently with adjacency lists.

Rust Implementation (Recursive)

use std::collections::{HashMap, HashSet};

type Graph = HashMap<i32, Vec<i32>>;

pub fn dfs(graph: &Graph, start: i32) -> Vec<i32> {
    let mut visited = HashSet::new();
    let mut order = Vec::new();

    dfs_helper(graph, start, &mut visited, &mut order);
    order
}

fn dfs_helper(
    graph: &Graph,
    node: i32,
    visited: &mut HashSet<i32>,
    order: &mut Vec<i32>,
) {
    visited.insert(node);
    order.push(node);

    if let Some(neighbors) = graph.get(&node) {
        for &neighbor in neighbors {
            if !visited.contains(&neighbor) {
                dfs_helper(graph, neighbor, visited, order);
            }
        }
    }
}

Rust Implementation (Iterative)

DFS can also be implemented using an explicit stack.

use std::collections::{HashMap, HashSet};

type Graph = HashMap<i32, Vec<i32>>;

pub fn dfs_iterative(graph: &Graph, start: i32) -> Vec<i32> {
    let mut visited = HashSet::new();
    let mut stack = vec![start];
    let mut order = Vec::new();

    while let Some(node) = stack.pop() {
        if visited.contains(&node) {
            continue;
        }

        visited.insert(node);
        order.push(node);

        if let Some(neighbors) = graph.get(&node) {
            // Reverse to mimic recursive order
            for &neighbor in neighbors.iter().rev() {
                if !visited.contains(&neighbor) {
                    stack.push(neighbor);
                }
            }
        }
    }

    order
}

Example Usage

fn main() {
    let mut graph: Graph = HashMap::new();

    graph.insert(1, vec![2, 3]);
    graph.insert(2, vec![1, 4, 5]);
    graph.insert(3, vec![1]);
    graph.insert(4, vec![2]);
    graph.insert(5, vec![2]);

    let traversal = dfs(&graph, 1);
    println!("{:?}", traversal);
}

Possible output:

[1, 2, 4, 5, 3]

Time and Space Complexity

Time Complexity

Space Complexity

BFS vs DFS (Quick Comparison)

When to Use DFS

DFS is ideal when:

• Exploring all possible paths
• Detecting cycles
• Topological sorting
• Solving puzzles and backtracking problems

Playground Links

Rust - Depth-First Search (DFS) - Recursive

Rust - Depth-First Search (DFS) - Iterative