Chapter 69

Home

Breadth First Search (BFS)

BFS explores level by level — all neighbours first, then neighbours of neighbours. It finds the shortest path in an unweighted graph because it visits nodes in order of distance from the start.

BFS Algorithm

C++ — BFS with distance tracking

vector dist(V, -1);
queue q;

dist[start] = 0;
q.push(start);

while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u]) {
        if (dist[v] == -1) {
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
}

// dist[v] = shortest path length from start to v

Rust — BFS

use std::collections::VecDeque;

let mut dist = vec![-1; V];
let mut q = VecDeque::new();
dist[start] = 0;
q.push_back(start);

while let Some(u) = q.pop_front() {
    for &v in &adj[u] {
        if dist[v] == -1 {
            dist[v] = dist[u] + 1;
            q.push_back(v);
        }
    }
}
BFS order: start → distance 1 → distance 2 → distance 3Queue ensures level-by-level ordering

💡 BFS vs DFS

BFS uses a queue (FIFO) — finds shortest path. DFS uses a stack (LIFO) — finds any path but not necessarily shortest. BFS memory use is O(width) of graph; DFS is O(depth).

Key Takeaways

Practice