Breadth-First Search (BFS)

Breadth-first search (BFS) is a graph traversal algorithm that explores a graph level by level. Starting from a source vertex, BFS visits all its immediate neighbors before moving on to their neighbors. This makes BFS particularly useful for finding the shortest path in unweighted graphs and for analyzing graph connectivity.

BFS works on both directed and undirected graphs and requires a queue to manage traversal order.

BFS Idea

The core idea behind BFS is simple:

1. Start from a given source vertex
2. Visit all directly connected neighbors
3. Move outward layer by layer
4. Ensure each vertex is visited only once

This guarantees that vertices are explored in increasing order of distance from the source.

Example Graph

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

Starting BFS from vertex A results in:

A → B → C → D → E

BFS Algorithm Steps

1. Mark the starting vertex as visited

2. Add it to a queue

3. While the queue is not empty:

   • Remove the front vertex
   • Visit all unvisited neighbors
   • Mark them visited and enqueue them

BFS Using Adjacency List

BFS is most commonly implemented using an adjacency list, as it allows efficient traversal of neighbors.

Rust Implementation

Below is a clean BFS implementation using an adjacency list and a queue.

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

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

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

    visited.insert(start);
    queue.push_back(start);

    while let Some(node) = queue.pop_front() {
        order.push(node);

        if let Some(neighbors) = graph.get(&node) {
            for &neighbor in neighbors {
                if !visited.contains(&neighbor) {
                    visited.insert(neighbor);
                    queue.push_back(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 = bfs(&graph, 1);
    println!("{:?}", traversal);
}

Output:

[1, 2, 3, 4, 5]

Time and Space Complexity

Time Complexity

Each vertex and edge is visited at most once.

Space Complexity

When to Use BFS

BFS is ideal when:

• Finding the shortest path in unweighted graphs
• Exploring all reachable vertices
• Detecting connected components
• Checking bipartite graphs

Limitations of BFS

• Requires additional memory for queue
• Not suitable for weighted shortest paths
• Can be slower than DFS in deep graphs

Playground Links

Rust - Breadth-First Search (BFS)