Depth-first search

Depth-first search (DFS) is a straightforward graph traversal technique. The algorithm begins at a starting node, and proceeds to all other nodes that are reachable from the starting node using the edges of the graph.

Depth-first search always follows a single path in the graph as long as it finds new nodes. After this, it returns to previous nodes and begins to explore other parts of the graph. The algorithm keeps track of visited nodes, so that it processes each node only once.

Example

Let us consider how depth-first search processes the following graph:

We may begin the search at any node of the graph; now we will begin the search at node 1.

The search first proceeds to node 2:

After this, nodes 3 and 5 will be visited:

The neighbors of node 5 are 2 and 3, but the search has already visited both of them, so it is time to return to the previous nodes. Also the neighbors of nodes 3 and 2 have been visited, so we next move from node 1 to node 4:

After this, the search terminates because it has visited all nodes.

The time complexity of depth-first search is $O(n+m)$ where $n$ is the number of nodes and $m$ is the number of edges, because the algorithm processes each node and edge once.

Implementation

Depth-first search can be conveniently implemented using recursion. The following function dfs begins a depth-first search at a given node. The function assumes that the graph is stored as adjacency lists in an array

#![allow(unused)]
fn main() {
const N:usize = 10;
let mut adj: [Vec<i32>; N]= Default::default();
println!("{adj:?}");
}

and also maintains an array

#![allow(unused)]
fn main() {
let mut visited: Vec<bool> = Vec::new();
println!("{visited:?}");
}

that keeps track of the visited nodes. Initially, each array value is false, and when the search arrives at node $s$, the value of visited[s] becomes true. The function can be implemented as follows:

#![allow(unused)]
fn main() {
const N:usize = 10;
let mut adj: [Vec<i32>; N]= Default::default();
let mut visited: Vec<bool> = Vec::new();
fn dfs(s: usize, adj: &[Vec<i32>],visited: &mut Vec<bool>){
    if visited[s] {return}
    visited[s] = true;
    // process node s
    for &u in &adj[s] {
        dfs(u as usize, adj, visited);
    }
}
}