Breadth-First Search (BFS) Algorithm

About This Module

This module provides an in-depth exploration of the breadth-first search (BFS) algorithm, a fundamental graph traversal technique. Students will learn to implement BFS in Rust, understand its computational complexity, and apply it to solve important graph problems such as shortest path finding and connected component detection. The module emphasizes both theoretical understanding and practical implementation skills.

Prework

Before this lecture, please read:

Introduction to Algorithms Chapter 22.2: "Breadth-first search" (if available)
The Rust Book Chapter 8.1: "Storing Lists of Values with Vectors" - https://doc.rust-lang.org/book/ch08-01-vectors.html
Rust std::collections::VecDeque documentation - https://doc.rust-lang.org/std/collections/struct.VecDeque.html

Pre-lecture Reflections

Why is BFS particularly useful for finding shortest paths in unweighted graphs?
How does the queue data structure enable BFS's level-by-level exploration?
What are some real-world applications where BFS would be the preferred search strategy?

Lecture

Learning Objectives

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

Implement the BFS algorithm using queues and proper graph traversal techniques
Analyze BFS's O(V+E) time complexity and understand why it achieves this bound
Apply BFS to solve shortest path problems in unweighted graphs
Use BFS for connected component detection in undirected graphs
Trace through BFS execution and predict its behavior on different graph structures

Sample graph

let n: usize = 10;
let mut 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)];
edges.sort();
println!("{:?}",edges);
let graph = Graph::create_undirected(n,&edges);
for (i, l) in graph.outedges.iter().enumerate() {
    println!("{} {:?}", i, *l);
}

[(0, 1), (0, 2), (1, 2), (1, 9), (2, 3), (2, 4), (4, 3), (4, 5), (4, 6), (5, 6), (6, 7), (6, 8), (8, 7)]
0 [1, 2]
1 [0, 2, 9]
2 [0, 1, 3, 4]
3 [2, 4]
4 [2, 3, 5, 6]
5 [4, 6]
6 [4, 5, 7, 8]
7 [6, 8]
8 [6, 7]
9 [1]




()

Breadth–first search (BFS)

General idea:

start from some vertex and explore its neighbors (distance 1)
then explore neighbors of neighbors (distance 2)
then explore neighbors of neighbors of neighbors (distance 3)
...

Our example: start from vertex 2

Whiteboard walk-through

Let's first walk through the process interactively, then look at the code implementaiton.

The following reorganizes the graph to group by number of steps from the starting node.

[first sample graph, grouped into layers]

Implementation: compute distances from vertex 2 via BFS -- I

distance[v]: distance of v from vertex 2 (None is unknown)

let start: Vertex = 2; // <= we'll start from this vertex

let mut distance: Vec<Option<u32>> = vec![None;graph.n];
distance[start] = Some(0); // <= we know this distance
distance

[None, None, Some(0), None, None, None, None, None, None, None]

queue: vertices to consider, they will arrive layer by layer

use std::collections::VecDeque;
let mut queue: VecDeque<Vertex> = VecDeque::new();
queue.push_back(start);
queue

[2]

Implementation: compute distances from vertex 2 via BFS -- II

Main loop:
$∙$ consider vertices one by one
$∙$ add their new neighbors to the processing queue

println!("{:?}",queue);
while let Some(v) = queue.pop_front() { // new unprocessed vertex
    println!("top {:?}",queue);
    for u in graph.outedges[v].iter() {
        if let None = distance[*u] { // consider all unprocessed neighbors of v
            distance[*u] = Some(distance[v].unwrap() + 1);
            queue.push_back(*u);
            println!("In {:?}",queue);
        }
    }
};

[2]
top []
In [0]
In [0, 1]
In [0, 1, 3]
In [0, 1, 3, 4]
top [1, 3, 4]
top [3, 4]
In [3, 4, 9]
top [4, 9]
top [9]
In [9, 5]
In [9, 5, 6]
top [5, 6]
top [6]
top []
In [7]
In [7, 8]
top [8]
top []

Implementation: compute distances from vertex 2 via BFS -- III

Compare results:

print!("vertex:distance");
for v in 0..graph.n {
    print!("   {}:{}",v,distance[v].unwrap());
}
println!();

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

What if we wanted the distance from all to all?

// let's wrap the previous code in a function
fn compute_and_print_distance_bfs(start: Vertex, graph: &Graph) {
    let mut distance: Vec<Option<u32>> = vec![None;graph.n];
    distance[start] = Some(0); // <= we know this distance
    let mut queue: VecDeque<Vertex> = VecDeque::new();
    queue.push_back(start);
    while let Some(v) = queue.pop_front() { // new unprocessed vertex
        for u in graph.outedges[v].iter() {
            if let None = distance[*u] { // consider all unprocessed neighbors of v
                distance[*u] = Some(distance[v].unwrap() + 1);
                queue.push_back(*u);
            }
        }
    }
    print!("vertex:distance");
    for v in 0..graph.n {
        print!("   {}:{}",v,distance[v].unwrap());
    }
    println!();
}

// Then loop to start BFS from each node
for i in 0..graph.n {
    println!("Distances from node {}", i);
    compute_and_print_distance_bfs(i, &graph);
}

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




()

Computational complexity of BFS

O(V+E) where V is the number of vertices and E is the number of edges

Why?

Two loops:

The outside loop goes through vertices and will go through every vertex and will only do so once!
The inside loop goes through the edges of that vertex.
But if you go through the edges of every vertex that is equal to the total number of edges. So it's not multiplicative but additive.

Strength of BFS

So we see one strength of BFS is that it is good at calculating distances.

Connected components via BFS

Connected component (in an undirected graph):

a maximal set of vertices that are connected

Sample graph:

let n: usize = 9;
let edges: Vec<(Vertex,Vertex)> = vec![(0,1),(0,2),(1,2),(2,4),(0,4),(5,7),(6,8)];
let graph = Graph::create_undirected(n, &edges);

Discovering vertices of a connected component via BFS

component[v]: v's component's number (None $\equiv$ not assigned yet)

type Component = usize;

/*
 * Loop through all the vertices connected to the passed in vertex and assign it the same 
 * component group number.
 */
fn mark_component_bfs(vertex:Vertex, // current vertex number
                      graph:&Graph,  // graph structure
                      component:&mut Vec<Option<Component>>, // the component assignment for each node 
                      component_no:Component  // the component group of the current vertex
                     ) {
    component[vertex] = Some(component_no);
    
    let mut queue = std::collections::VecDeque::new();
    queue.push_back(vertex);
    
    while let Some(v) = queue.pop_front() {
        for w in graph.outedges[v].iter() {
            if let None = component[*w] {   // if node not assigned to a component group yet
                component[*w] = Some(component_no);  // assign it the current component number
                queue.push_back(*w);      // push it onto the queue to search since it is connected
            }
        }
    }
}

Marking all connected components

Loop over all unassigned vertices and assign component numbers

// Vec of component assignments for each node, initialized to None
let mut component: Vec<Option<Component>> = vec![None;n];

let mut component_count = 0;

for v in 0..n {
    if let None = component[v] {
        component_count += 1;
        mark_component_bfs(v, &graph, &mut component, component_count);
    }
};

// Let's verify the assignment!
print!("{} components:\n[  ",component_count);
for v in 0..n {
    print!("{}:{}  ",v,component[v].unwrap());
}
println!("]\n");

4 components:
[  0:1  1:1  2:1  3:2  4:1  5:3  6:4  7:3  8:4  ]

Question: What is complexity of this algorithm?

It is also $O (V + E)$ .

DS210 Course Notes