Depth-First Search (DFS) Algorithm

About This Module

This module covers the depth-first search (DFS) algorithm, a fundamental graph traversal technique that explores as far as possible along each branch before backtracking. Students will learn to implement DFS in Rust, understand its applications in topological sorting and strongly connected components, and compare it with BFS. The module emphasizes both recursive and iterative implementations while exploring DFS's unique strengths in graph analysis.

Prework

Before this lecture, please read:

• Introduction to Algorithms Chapter 22.3: "Depth-first search" (if available)
• The Rust Book Chapter 6.1: "Defining and Instantiating Structs" - https://doc.rust-lang.org/book/ch06-01-defining-structs.html
• The Rust Book Chapter 5.3: "Method Syntax" - https://doc.rust-lang.org/book/ch05-03-method-syntax.html

Pre-lecture Reflections

1. How does DFS's exploration pattern differ from BFS, and when might this be advantageous?
2. What are the advantages and challenges of implementing DFS recursively vs. iteratively?
3. In what types of graph problems would DFS be preferred over BFS?

Lecture

Learning Objectives

By the end of this lecture, you should be able to:

• Implement DFS using both recursive and iterative approaches
• Understand DFS's applications in topological sorting and cycle detection
• Analyze the computational complexity and memory usage of DFS
• Apply DFS to find strongly connected components in directed graphs
• Compare DFS and BFS for different graph analysis tasks

DFS Example

Depth–First Search (DFS) -- I

General idea:

• keep going to an unvisited vertex
• when stuck make a step back and try again

Depth–First Search (DFS) -- II

General idea:

• keep going to an unvisited vertex
• when stuck make a step back and try again

Depth–First Search (DFS) -- III

General idea:

• keep going to an unvisited vertex
• when stuck make a step back and try again

Depth–First Search (DFS) -- IV

General idea:

• keep going to an unvisited vertex
• when stuck make a step back and try again

Depth–First Search (DFS) -- V

General idea:

• keep moving to an unvisited neighbor
• when stuck make a step back and try again

Depth–First Search (DFS) -- VI

General idea:

• keep going to an unvisited vertex
• when stuck make a step back and try again

Depth–First Search (DFS) -- VII

General idea:

• keep going to an unvisited vertex
• when stuck make a step back and try again

Depth–First Search (DFS) -- VIII

General idea:

• keep going to an unvisited vertex
• when stuck make a step back and try again

Depth–First Search (DFS) -- IX

General idea:

• keep going to an unvisited vertex
• when stuck make a step back and try again

Depth–First Search (DFS) -- X

General idea:

• keep going to an unvisited vertex
• when stuck make a step back and try again

Depth–First Search (DFS) -- XI

General idea:

• keep going to an unvisited vertex
• when stuck make a step back and try again

Depth–First Search (DFS) -- XII

General idea:

• keep going to an unvisited vertex
• when stuck make a step back and try again

Depth–First Search (DFS) -- XIII

General idea:

• keep going to an unvisited vertex
• when stuck make a step back and try again

Depth–First Search (DFS) -- XIV

General idea:

• keep going to an unvisited vertex
• when stuck make a step back and try again

Depth–First Search (DFS) -- XV

General idea:

• keep going to an unvisited vertex
• when stuck make a step back and try again

Our sample graph from BFS

DFS Implementation

fn dfs(vertex:Vertex,  // starting vertex
       graph: &Graph,  // graph structure
       d: usize,       // distance of node connected to passed in vertex
       visited: &mut Vec<bool>,  // Vec of bools indicating if we visited a node 
       distance: &mut Vec<usize>   // Vec of distances of each vertex from the starting vertex
      ){
    // loop through every vertex connected to the current vertex
    for w in graph.outedges[vertex].iter() {
      if visited[*w] == false {
        distance[*w] = d;
        visited[*w] = true;
        dfs(*w, graph, d+1, visited, distance);
      }
    }
}

let n: usize = 10;
let edges: ListOfEdges = vec![(0,1),(0,2),(1,2),(2,4),(2,3),(4,3),(4,5),(5,6),(4,6),(6,8),(6,7),(8,7),(1,9)];
let graph = Graph::create_undirected(n,&edges);
let mut visited = vec![false;graph.n];
let mut distance = vec![0;graph.n];

visited[2] = true;
distance[2] = 0;
dfs(2, &graph, 1, &mut visited, &mut distance);
println!("vertex:distance");
for v in 0..graph.n {
    print!("   {}:{}",v,distance[v]);
}
println!();

// For comparison this was the distance from bfs 
// vertex:distance   0:1   1:1   2:0   3:1   4:1   5:2   6:2   7:3   8:3   9:2

vertex:distance
   0:1   1:2   2:0   3:1   4:2   5:3   6:4   7:5   8:6   9:3