Breadth-first search

Breadth-first search (BFS) visits the nodes in increasing order of their distance from the starting node. Thus, we can calculate the distance from the starting node to all other nodes using breadth-first search. However, breadth-first search is more difficult to implement than depth-first search.

Breadth-first search goes through the nodes one level after another. First the search explores the nodes whose distance from the starting node is 1, then the nodes whose distance is 2, and so on. This process continues until all nodes have been visited.

Example

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

Suppose that the search begins at node 1. First, we process all nodes that can be reached from node 1 using a single edge:

After this, we proceed to nodes 3 and 5:

Finally, we visit node 6:

Now we have calculated the distances from the starting node to all nodes of the graph. The distances are as follows:

Like in depth-first search, the time complexity of breadth-first search is $O(n+m)$, where $n$ is the number of nodes and $m$ is the number of edges.

Implementation

Breadth-first search is more difficult to implement than depth-first search, because the algorithm visits nodes in different parts of the graph. A typical implementation is based on a queue that contains nodes. At each step, the next node in the queue will be processed.

The following code assumes that the graph is stored as adjacency lists and maintains the following data structures:

#![allow(unused)]
fn main() {
use std::collections::VecDeque;
const N:usize = 10;
let mut q = VecDeque::<usize>::new();
let mut visited = [false; 10];
let mut distance = [0; 10];
}

The queue q contains nodes to be processed in increasing order of their distance. New nodes are always added to the end of the queue, and the node at the beginning of the queue is the next node to be processed. The array visited indicates which nodes the search has already visited, and the array distance will contain the distances from the starting node to all nodes of the graph.

The search can be implemented as follows, starting at node $x$:

#![allow(unused)]
fn main() {
use std::collections::VecDeque;
const N:usize = 10;
let mut q = VecDeque::<usize>::new();
let mut visited = [false; 10];
let mut distance = [0; 10];
let mut adj: [Vec<usize>; N]= Default::default();
let x = 0;
visited[x] = true;
distance[x] = 0;
q.push_front(x);
while !q.is_empty() {
    let s = q.pop_front().unwrap();
    // process node s
    for &u in &adj[s] {
        if visited[u] {continue}
        visited[u] = true;
        distance[u] = distance[s]+1;
        q.push_front(u);
    }
}
}