Back to Graph Theory Series

Breadth-First Search (BFS)

August 30, 2026 Wasil Zafar 14 min read

The algorithm that explores a graph one ring at a time — and the reason it always finds the shortest path first in an unweighted graph.

Contents

  1. Working Principle
  2. Interactive Demo
  3. Complexity Analysis
  4. Implementation
  5. Correctness Proof Sketch
  6. Real-World Applications
  7. Limitations

Working Principle

Breadth-First Search: Explore One Layer at a Time

Think of Breadth-First Search (BFS) as a wave spreading outward from a starting vertex. It first visits the start, then all vertices 1 edge away, then all vertices 2 edges away, then 3 edges away, and so on.

S A B C D E F Distance 0 Distance 1 Distance 2 BFS moves → outward

BFS keeps the vertices it has discovered in a queue. A queue works like a line of people: the vertex that enters first is also the first one processed (FIFO — First In, First Out).

Queue after exploring S:
Front → A B ← Back

A must be processed before vertices discovered from A or B can jump ahead of it. This is what keeps BFS moving layer by layer.

How BFS proceeds

  1. Put the starting vertex into the queue and mark it as visited.
  2. Remove the vertex at the front of the queue.
  3. Look at all of its neighbors.
  4. For every neighbor not seen before, mark it as visited and add it to the back of the queue.
  5. Repeat until the queue is empty.
💡 Why does BFS find shortest paths?

BFS never skips ahead to a farther layer. Every vertex at distance 1 is discovered before any vertex at distance 2, every vertex at distance 2 before distance 3, and so on. Therefore, the first time BFS reaches a vertex, it has reached it using the fewest possible number of edges.

BFS and DFS (the next deep dive) differ only in the data structure holding the frontier: BFS uses a queue and explores broadly; DFS uses a stack (or recursion, which is an implicit stack) and dives deep. Every other line of the algorithm is nearly identical — which is why the two are almost always taught, and implemented, side by side.

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.

BFS vs DFS — Live Comparison

Unvisited Current In Queue/Stack Visited
BFS: Start at Node A

Click Next to step through BFS first, then DFS on the same graph.

Queue: [A] Step 1 / 10

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}$$

Why O(V+E) and Not O(V) or O(E) Alone?

Neither term alone bounds the work: a graph can have \(V\) vertices but \(0\) edges (isolated vertices still cost \(O(1)\) each to visit), or very few vertices but many edges (a dense graph). \(O(V+E)\) — sometimes called linear in the size of the graph — is the tight bound that accounts for both costs honestly.

Implementation

from collections import defaultdict, deque

def bfs(adj, source):
    """
    Performs Breadth-First Search (BFS) 
    to find shortest paths in an unweighted graph.
    
    Args:
        adj (dict): Adjacency list representation 
        of the graph, e.g., {node: [neighbors]}.
        source: The starting node for the search traversal.
        
    Returns:
        dist (dict): Maps each reachable node 
        to its minimum distance (edge count) from source.
        parent (dict): Maps each reachable node to the node 
        that preceded it, used for path reconstruction.
    """
    # Initialize distances: source node is distance 0 from itself
    dist = {source: 0}
    
    # Initialize parent pointers: source node has no parent
    parent = {source: None}
    
    # Queue (FIFO) keeps track of nodes to explore next, 
    #starting with the source
    queue = deque([source])

    # Process nodes layer by layer until the queue is empty
    while queue:
        # Remove and retrieve the oldest node from the front of the queue
        u = queue.popleft()
        
        # Explore all immediate neighbors of current node 'u'
        for v in adj[u]:
            # 'v not in dist' acts as the visited check.
            # In unweighted BFS, the first time 
            #we discover a node yields its shortest path.
            if v not in dist:
                dist[v] = dist[u] + 1  # Record distance (one step further than parent 'u')
                parent[v] = u          # Record 'u' as the predecessor of 'v'
                queue.append(v)        # Add 'v' to queue to process its neighbors later

    return dist, parent

def reconstruct_path(parent, target):
    """
    Backtracks from target to source using the parent map to rebuild the path.
    
    Args:
        parent (dict): The predecessor mapping generated by bfs().
        target: The end node to construct a path to.
        
    Returns:
        list: The ordered path from source to target, 
        or [] if target was unvisited.
    """
    # Handle unvisited target nodes
    if target not in parent:
        return []
        
    path = []
    # Walk backward from target up to source (where parent[source] is None)
    while target is not None:
        path.append(target)
        target = parent[target]  # Move to predecessor
        
    # Reverse list since we backtracked from target -> source
    return path[::-1]

# Define an undirected graph using an adjacency list with defaultdict
# defaultdict(list) ensures accessing an unlisted node 
# returns an empty list [] instead of KeyErrors

adj = defaultdict(list, {
    "A": ["B", "C"], 
    "B": ["A", "D", "E"], 
    "C": ["A", "E", "F"],
    "D": ["B"], 
    "E": ["B", "C"], 
    "F": ["C"],
})

# Run BFS algorithm starting from node "A"
dist, parent = bfs(adj, "A")

# Output shortest distance from 'A' to all reachable nodes
print("Distances from A:", dist)
# Output: {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 2}

# Reconstruct and print the specific shortest route from 'A' to 'F'
print("Shortest path A->F:", reconstruct_path(parent, "F"))
# Output: ['A', 'C', 'F']

#include <vector>                             // Include vector container for dynamic array storage
#include <queue>                              // Include queue container for breath-first search
#include <unordered_map>                      // Include hash map for graph lookup tables
#include <iostream>                           // Include iostream for standard console input output
using namespace std;                          // Use standard namespace to simplify basic types

pair<unordered_map<string,int>, unordered_map<string,string>> // Define function return type holding distance parent maps
bfs(unordered_map<string, vector<string>>& adj, const string& source) { // Perform breadth-first search from given start node
    unordered_map<string, int> dist;          // Map each visited node to short distance
    unordered_map<string, string> parent;     // Map child node to its immediate predecessor
    queue<string> q;                          // Queue to manage frontier nodes during traversal

    dist[source] = 0;                         // Set distance of starting source node to zero
    q.push(source);                           // Push starting source node into exploration queue

    while (!q.empty()) {                      // Process queue elements until all reachable nodes visited
        string u = q.front(); q.pop();        // Extract next node and remove from queue
        for (const string& v : adj[u]) {      // Iterate over all neighbor nodes of node u
            if (dist.find(v) == dist.end()) {   // first time discovered
                dist[v] = dist[u] + 1;        // Calculate and set distance for new node
                parent[v] = u;                // Record parent node to track path origins
                q.push(v);                    // Add newly discovered node to search queue
            }
        }
    }
    return {dist, parent};                    // Return short distance and parent tracking maps
}

int main() {                                  // Entry point of C++ console application execution
    unordered_map<string, vector<string>> adj = { // Define sample graph adjacency list with edges
        {"A", {"B", "C"}}, {"B", {"A", "D", "E"}}, {"C", {"A", "E", "F"}},
        {"D", {"B"}}, {"E", {"B", "C"}}, {"F", {"C"}}
    };

    auto [dist, parent] = bfs(adj, "A");      // Run search algorithm starting from root node A
    cout << "Distance A->F: " << dist["F"] << endl;   // 2
    return 0;                                 // Return zero status code for successful execution
}

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

Case Study

Social-Network "Degrees of Separation"

LinkedIn's "2nd-degree connection" and "3rd-degree connection" labels are literally BFS distance-1 and distance-2 (and beyond) layers computed from your profile as the source vertex. The same layer-by-layer structure powers friend-of-friend recommendation systems and the classic "six degrees of separation" experiments.

Social GraphsRecommendations

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

BFS Does Not Handle Weighted Edges

BFS's shortest-path guarantee relies entirely on every edge counting as exactly "1 step." The moment edges have different weights, a path with more edges can be cheaper than a path with fewer — BFS will get this wrong. That's exactly the gap Dijkstra's algorithm fills.

Related Deep Dives

Graph Theory Series

Browse all parts of the series plus every algorithm deep dive.

View Full Series
Depth-First Search (DFS)

The stack-based sibling of BFS — same interactive demo, different exploration order.

Read Deep Dive
Dijkstra's Algorithm

BFS generalized to weighted edges via a priority queue.

Read Deep Dive