Breadth-First Search (BFS)

Working Principle

Breadth-First Search explores a graph outward in layers: first the source vertex, then every neighbor at distance 1, then every unvisited vertex at distance 2, and so on. It achieves this using a queue (FIFO): enqueue the source, then repeatedly dequeue a vertex, mark it visited, and enqueue every unvisited neighbor.

Because a queue always processes vertices in the order they were discovered, and because a vertex is only ever enqueued the first time it's reached, BFS guarantees that a vertex at true graph distance \(d\) from the source is dequeued only after every vertex at distance \(< d\) has already been dequeued. This "layer-by-layer" guarantee is the entire reason BFS solves shortest paths in unweighted graphs.

def bfs_pseudocode(graph, source):
    """
    Precondition: `graph` maps each vertex to a list of neighbors.
    Postcondition: dist[v] = shortest number of edges from source to v
                   (or None if v is unreachable).
    """
    from collections import deque
    dist = {source: 0}
    queue = deque([source])
    while queue:
        u = queue.popleft()               # FIFO: earliest-discovered vertex first
        for v in graph[u]:
            if v not in dist:             # first time v is ever discovered
                dist[v] = dist[u] + 1
                queue.append(v)
    return dist

Interactive Demo

Step through BFS (then DFS, in the next deep dive) on the same 6-node graph. Watch how the queue processes nodes strictly in discovery order.

Complexity Analysis

Every vertex is enqueued at most once (guarded by the "first time discovered" check), so the outer loop runs \(O(V)\) times. Every edge is examined at most twice in an undirected graph (once from each endpoint) or once in a directed graph, so the total work across all iterations of the inner loop is \(O(E)\). Combined:

$$\text{Time: } O(V + E) \qquad \text{Space: } O(V) \text{ for the visited/distance map and the queue}$$

Implementation

from collections import defaultdict, deque

def bfs(adj, source):
    """
    adj: dict[vertex] -> list[vertex]  (adjacency list)
    Returns: (dist, parent) where dist[v] is the shortest edge-count
             from source to v, and parent[v] lets you reconstruct the path.
    """
    dist = {source: 0}
    parent = {source: None}
    queue = deque([source])

    while queue:
        u = queue.popleft()
        for v in adj[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                parent[v] = u
                queue.append(v)

    return dist, parent

def reconstruct_path(parent, target):
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]

# Graph from the interactive demo
adj = defaultdict(list, {
    "A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "E", "F"],
    "D": ["B"], "E": ["B", "C"], "F": ["C"],
})

dist, parent = bfs(adj, "A")
print("Distances from A:", dist)                       # {'A': 0, 'B': 1, 'C': 1, ...}
print("Shortest path A->F:", reconstruct_path(parent, "F"))  # ['A', 'C', 'F']

#include <vector>
#include <queue>
#include <unordered_map>
#include <iostream>
using namespace std;

pair<unordered_map<string,int>, unordered_map<string,string>>
bfs(unordered_map<string, vector<string>>& adj, const string& source) {
    unordered_map<string, int> dist;
    unordered_map<string, string> parent;
    queue<string> q;

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

    while (!q.empty()) {
        string u = q.front(); q.pop();
        for (const string& v : adj[u]) {
            if (dist.find(v) == dist.end()) {   // first time discovered
                dist[v] = dist[u] + 1;
                parent[v] = u;
                q.push(v);
            }
        }
    }
    return {dist, parent};
}

int main() {
    unordered_map<string, vector<string>> adj = {
        {"A", {"B", "C"}}, {"B", {"A", "D", "E"}}, {"C", {"A", "E", "F"}},
        {"D", {"B"}}, {"E", {"B", "C"}}, {"F", {"C"}}
    };

    auto [dist, parent] = bfs(adj, "A");
    cout << "Distance A->F: " << dist["F"] << endl;   // 2
    return 0;
}

import java.util.*;

class BFS {
    static Map<String, Integer> bfs(Map<String, List<String>> adj, String source) {
        Map<String, Integer> dist = new HashMap<>();
        Map<String, String> parent = new HashMap<>();
        Queue<String> queue = new LinkedList<>();

        dist.put(source, 0);
        queue.add(source);

        while (!queue.isEmpty()) {
            String u = queue.poll();
            for (String v : adj.getOrDefault(u, Collections.emptyList())) {
                if (!dist.containsKey(v)) {         // first time discovered
                    dist.put(v, dist.get(u) + 1);
                    parent.put(v, u);
                    queue.add(v);
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        Map<String, List<String>> adj = new HashMap<>();
        adj.put("A", Arrays.asList("B", "C"));
        adj.put("B", Arrays.asList("A", "D", "E"));
        adj.put("C", Arrays.asList("A", "E", "F"));
        adj.put("D", Arrays.asList("B"));
        adj.put("E", Arrays.asList("B", "C"));
        adj.put("F", Arrays.asList("C"));

        Map<String, Integer> dist = bfs(adj, "A");
        System.out.println("Distance A->F: " + dist.get("F"));  // 2
    }
}

Correctness Proof Sketch

The proof is a direct application of the induction technique from Part 1. Claim: when BFS finishes, \(\text{dist}[v]\) equals the true shortest-path distance (in edges) from the source to \(v\), for every reachable \(v\).

Loop invariant: at every point during execution, the queue contains vertices from at most two consecutive distance layers, ordered so that all layer-\(k\) vertices precede all layer-\((k+1)\) vertices. Base case: initially the queue holds only the source at layer 0. Inductive step: when a layer-\(k\) vertex is dequeued and processed, any newly discovered neighbor is assigned distance \(k+1\) and appended — preserving the ordering. Since the queue is strictly FIFO, no layer-\((k+1)\) vertex is ever dequeued before all layer-\(k\) vertices are dequeued, and a vertex's distance is only ever set once (on first discovery) — so it can never be set to anything other than the true minimum.

Real-World Applications

Other standard uses: unweighted shortest paths, testing whether a graph is bipartite (2-color each BFS layer alternately and check for same-layer edges), finding connected components, and web-crawler frontier management (crawl breadth-first from seed URLs).

Limitations