Breadth-First Search (BFS)

Breadth-First Search (BFS) is a graph traversal algorithm that explores a graph one layer at a time: it visits every neighbor of the starting node before moving on to their neighbors, then their neighbors’ neighbors, and so on. Because it expands outward in rings, BFS is the standard tool for finding the shortest path (measured in number of edges) in an unweighted graph, and it powers things like degrees-of-separation calculations, shortest-route finding in mazes and grids, and level-order processing of trees. This lesson covers how BFS works under the hood, its complexity, several worked implementations, and the mistakes that most commonly break it.

Overview: How BFS Works

Imagine a small social network: Alice is directly connected to Bob and Carol. Bob is connected to Dana and Erin. Carol is connected to Frank. If you want to know everyone within two connections of Alice, you would not chase one long chain all the way to the end — that is what Depth-First Search does. Instead you would first list Alice’s direct friends (Bob, Carol), and only after you’ve accounted for all of them would you look at their friends (Dana, Erin, Frank). That expand-outward-in-rings behavior is exactly what BFS does, and it’s why BFS is the natural choice whenever you need the fewest steps between two nodes.

The algorithm needs two pieces of bookkeeping: a queue (a first-in-first-out structure, typically collections.deque in Python) that holds nodes waiting to be explored, and a visited set that records every node that has already been discovered so it is never enqueued twice. The core loop is:

1. Add the starting node to the queue and mark it visited.
2. While the queue is not empty, remove (dequeue) the node at the front.
3. For each of that node’s neighbors, if the neighbor has not been visited, mark it visited and add it to the back of the queue.
4. Repeat until the queue is empty.

The queue is what makes this breadth-first instead of depth-first. Because nodes are removed in the same order they were added (FIFO), every node at distance 1 from the start is fully processed before any node at distance 2 is even looked at. This guarantees that the first time BFS reaches any node, it has done so via a shortest possible path (in edge count) — a property DFS does not have, since DFS can plunge deep down one branch before circling back.

It is critical to mark a node as visited the moment it is enqueued, not when it is later dequeued. If you wait until dequeue time, the same node can be pushed onto the queue multiple times by different neighbors before it is ever processed, wasting work and — on a graph with cycles — potentially never letting the queue drain. See Common Mistakes below for exactly this bug.

Choosing a graph representation

BFS works over any representation of a graph, but the choice affects performance. An adjacency list (a dictionary mapping each node to a list of its neighbors, as used in every example below) is the right default for most real graphs, which tend to be sparse (few edges relative to the number of possible pairs) — looking up a node’s neighbors costs time proportional to its degree. An adjacency matrix (a 2D grid where cell [i][j] is truthy if an edge exists) gives O(1) checks for whether an edge exists between two nodes, which is handy for dense graphs, but forces BFS to scan an entire row of size V to find a vertex’s neighbors, which is wasteful when most graphs are sparse.

Time and Space Complexity

Let V be the number of vertices (nodes) and E be the number of edges. Every vertex is enqueued exactly once and dequeued exactly once, thanks to the visited set — so the total work spent dequeuing nodes is O(V). Every edge is examined once per direction while scanning a node’s neighbor list (twice total for an undirected graph, but constants are dropped in Big-O) — so the total work spent scanning adjacency lists is O(E). Added together, BFS on an adjacency list runs in O(V + E) time.

Representation / Case	Time	Space	Why
Adjacency list (typical)	O(V + E)	O(V)	Each vertex processed once; each edge scanned once from its source; visited set and queue each hold at most V entries.
Adjacency matrix	O(V²)	O(V)	Finding a vertex’s neighbors means scanning a full row of length V, for every one of the V vertices.
Grid / 2D maze (R rows, C cols)	O(R × C)	O(R × C)	Each cell is a node with up to 4 neighbors; the visited set can track up to R×C cells.

Unlike some algorithms, BFS has no meaningfully different best/average/worst case for a fixed graph — it always visits every reachable vertex and edge exactly once, so O(V + E) is simultaneously the best, average, and worst case for a full traversal. If you stop early upon finding a specific target, the actual work done can be less, but the worst case — the target being the very last node discovered, or absent entirely — is still O(V + E). Space is dominated by the visited set and the queue, both of which can hold up to O(V) nodes in the worst case (for example, a star graph where the center connects to every other node, so all of them get enqueued right after step one).

Examples

Example 1: Basic BFS traversal

The following function performs a standard BFS traversal starting from a given node and returns the order in which nodes were visited, using a six-node graph stored as an adjacency list: A connects to B and C; B connects to A, D, and E; C connects to A and F; D connects to B; E connects to B and F; and F connects to C and E.

from collections import deque


def bfs_traversal(graph: dict[str, list[str]], start: str) -> list[str]:
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order


graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E'],
}

result = bfs_traversal(graph, 'A')
print(result)

Output:

['A', 'B', 'C', 'D', 'E', 'F']

Tracing this: we start with visited = {A} and queue = [A]. Popping A visits it, discovers B and C (both unvisited), and enqueues them, leaving queue = [B, C]. Popping B discovers D and E (A is already visited), leaving queue = [C, D, E]. Popping C discovers F, leaving queue = [D, E, F]. D, E, and F are then popped in turn, but every one of their neighbors is already visited, so nothing new is added and the queue drains to empty. The final order — A, B, C, D, E, F — is exactly what gets printed.

Example 2: Shortest path with parent pointers

BFS is also the standard way to reconstruct an actual shortest path, not just its length. The trick is to record, for every newly discovered node, which node discovered it (its parent) — then walk backward through those parent pointers once the target is reached.

from collections import deque


def bfs_shortest_path(graph: dict[str, list[str]], start: str, target: str) -> list[str] | None:
    visited = {start}
    queue = deque([start])
    parent = {start: None}
    while queue:
        node = queue.popleft()
        if node == target:
            path = []
            while node is not None:
                path.append(node)
                node = parent[node]
            path.reverse()
            return path
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = node
                queue.append(neighbor)
    return None


graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E'],
}

path = bfs_shortest_path(graph, 'A', 'F')
print(path)
print(f'Shortest path length: {len(path) - 1} edges')

Output:

['A', 'C', 'F']
Shortest path length: 2 edges

Starting from A looking for F: A is dequeued first (not the target), discovering B and C with parent A. B is dequeued next (not the target), discovering D and E with parent B. C is dequeued next (not the target), discovering F with parent C. D and E are dequeued but add nothing new. Finally F is dequeued — since it’s the target, the function walks backward: F to parent C to parent A to parent None, producing the reversed path [F, C, A], then reverses it to [A, C, F]. That’s a 2-edge path (A to C to F), which is indeed the shortest way to reach F, even though A to B to E to F also exists and is 3 edges long.

Example 3: Shortest path through a grid

A very common real-world use of BFS is finding the shortest path through a grid or maze, such as the minimum number of moves through a warehouse floor plan where 1 marks a wall and 0 marks open floor. Each grid cell is treated as a node connected to its up/down/left/right neighbors.

from collections import deque


def shortest_path_grid(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    if grid[0][0] == 1 or grid[rows - 1][cols - 1] == 1:
        return -1
    visited = {(0, 0)}
    queue = deque([(0, 0, 0)])
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while queue:
        row, col, distance = queue.popleft()
        if (row, col) == (rows - 1, cols - 1):
            return distance
        for d_row, d_col in directions:
            new_row, new_col = row + d_row, col + d_col
            if (0 <= new_row < rows and 0 <= new_col < cols
                    and (new_row, new_col) not in visited
                    and grid[new_row][new_col] == 0):
                visited.add((new_row, new_col))
                queue.append((new_row, new_col, distance + 1))
    return -1


grid = [
    [0, 0, 1, 0],
    [1, 0, 1, 0],
    [0, 0, 0, 0],
    [0, 1, 1, 0],
]

steps = shortest_path_grid(grid)
print(f'Shortest path length: {steps}')

Output:

Shortest path length: 6

The grid has walls blocking the direct routes, so BFS has to route around them: from (0,0) it must go right to (0,1), down to (1,1), down to (2,1), then across through (2,2) and (2,3) before finally dropping down to the target (3,3) — six moves in total. Because BFS explores in order of distance, the moment it dequeues (3,3) it’s guaranteed no shorter route exists, so it returns immediately.

How BFS Works, Step by Step

Consider the same six-node graph as above, and trace BFS starting from 'A':

Step	Node Dequeued	Already-Visited Neighbors (skipped)	Newly Discovered & Enqueued	Queue After This Step
0 (start)	—	—	A	[A]
1	A	—	B, C	[B, C]
2	B	A	D, E	[C, D, E]
3	C	A	F	[D, E, F]
4	D	B	—	[E, F]
5	E	B, F	—	[F]
6	F	C, E	—	[]

Notice the order nodes get dequeued — A, B, C, D, E, F — matches the printed output of Example 1 exactly, because a node is appended to order the moment it’s dequeued. Also notice that by the time F is dequeued at step 6, both of its neighbors (C and E) are already visited, so no new work happens; the queue empties and the loop ends. This is also why bfs_distances in the Common Mistakes section correctly reports F at distance 2: F was first discovered while processing C (distance 1 + 1 = 2), and by the time E is processed and could have rediscovered F, F is already marked visited so its distance is never overwritten.

Common Mistakes

Mistake 1: Marking a node visited too late

A common bug is checking whether a neighbor already exists in a distances/visited collection before deciding to record it, but then enqueueing that neighbor unconditionally regardless of the outcome:

def bfs_distances_wrong(graph, start):
    distances = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in distances:
                distances[neighbor] = distances[node] + 1
            queue.append(neighbor)  # BUG: enqueues neighbor even if already visited
    return distances

The if neighbor not in distances check correctly guards the distance calculation, but queue.append(neighbor) runs unconditionally, outside the if. Every time an already-visited node is dequeued, it re-adds all of its neighbors — including ones already processed — back onto the queue. On a graph that contains even one cycle, the queue grows faster than it shrinks and the loop never terminates. The fix is to guard the enqueue with the same visited check, marking a node visited the moment it’s added to the queue, not later:

from collections import deque


def bfs_distances(graph: dict[str, list[str]], start: str) -> dict[str, int]:
    distances = {start: 0}
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                distances[neighbor] = distances[node] + 1
                queue.append(neighbor)
    return distances


graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E'],
}

result = bfs_distances(graph, 'A')
print(result)

Output:

{'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 2}

This mirrors the pattern already used in Example 1: check visited, add to visited, then enqueue — all three happen together, so nothing is ever queued twice.

Mistake 2: Using a list instead of a set for the visited check

This next version still produces the correct traversal order, which is exactly why it’s dangerous — nothing about the output reveals it’s slower than it should be:

from collections import deque


def bfs_traversal_slow(graph: dict[str, list[str]], start: str) -> list[str]:
    visited = [start]  # MISTAKE: a list makes 'in' checks O(n) instead of O(1)
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:  # O(n) scan on every single check
                visited.append(neighbor)
                queue.append(neighbor)
    return order


graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E'],
}

print(bfs_traversal_slow(graph, 'A'))

Output:

['A', 'B', 'C', 'D', 'E', 'F']

The result is identical to Example 1. The problem is if neighbor not in visited: checking list membership with in is O(n) — Python has to scan the list entry by entry — while checking in on a set is O(1) on average, because a set is backed by a hash table. With a list as visited, the overall traversal degrades from O(V + E) toward O(V × (V + E)), since each of the up-to-V membership checks can itself cost up to O(V). On a graph with a handful of nodes you would never notice; on a graph with a million nodes, this is the difference between milliseconds and minutes. Always use a set (or a dict, if you need to attach data like distance) for visited, never a list.

Best Practices

• Use collections.deque for the queue, never a plain list with list.pop(0) — popping from the front of a Python list is O(n) because every remaining element has to shift, which silently turns an O(V + E) BFS into O(V²).
• Mark a node as visited the instant you enqueue it, not when you dequeue it — this is the single most important correctness rule in BFS, and it prevents duplicate work or non-termination on cyclic graphs.
• Reach for BFS when you need the shortest path in an unweighted graph, level-order output, or the minimum number of steps between states (grids, word ladders, puzzle states). Reach for DFS instead when you just need to visit every node, check connectivity, detect cycles, or do backtracking.
• For weighted graphs, BFS’s shortest-path guarantee no longer holds — use Dijkstra’s algorithm (or 0-1 BFS when edge weights are only 0 or 1) instead.
• When BFS needs to answer whether a path exists or how long it is, track a parent map (Example 2) or a distances map (the Mistake 1 fix) rather than trying to reconstruct that information after the fact.
• On very large or deeply connected graphs, BFS’s iterative, queue-based nature is an advantage over recursive DFS: it has no call-stack depth to worry about, so it can’t hit Python’s recursion limit.

Practice Exercises

1. Word Ladder distance: Given a start word, a target word, and a list of valid words of the same length, find the minimum number of one-letter changes needed to go from start to target, where every intermediate word must also be in the list. Model each word as a node and connect two words if they differ by exactly one letter, then run BFS. Hint: for start='hit', target='cog', and word list ['hot', 'dot', 'dog', 'lot', 'log', 'cog'], the answer is 5 transformations.
2. Rotting oranges: Given a grid where 2 marks a rotten orange, 1 marks a fresh orange, and 0 marks an empty cell, find the minimum number of minutes until no fresh orange remains, given that rot spreads to orthogonally-adjacent fresh oranges once per minute. Hint: this is a multi-source BFS — seed the queue with every rotten orange at once, not just one.
3. Level counter: Modify bfs_traversal from Example 1 so it returns a list of lists, where each inner list holds all the nodes at one distance ring from the start (for the example graph starting at A: [['A'], ['B', 'C'], ['D', 'E', 'F']]). Hint: process the queue one full level at a time, using len(queue) as a snapshot of how many nodes belong to the current level before any of them get expanded.

Summary

• BFS explores a graph level by level using a FIFO queue, guaranteeing it finds the shortest path (by edge count) in an unweighted graph.
• Time complexity is O(V + E) on an adjacency list, since every vertex is dequeued once and every edge is scanned once; it becomes O(V²) on an adjacency matrix because each vertex lookup scans a full row.
• Space complexity is O(V) for the visited set and the queue.
• Always mark a node visited at enqueue time, not dequeue time — marking too late causes duplicate work and can make the queue never drain on cyclic graphs.
• Always back visited with a set (O(1) average membership check), never a list (O(n) membership check) — this bug is silent because the output stays correct while performance quietly degrades.
• Use BFS for shortest unweighted paths, level-order processing, and minimum-steps problems; use DFS for plain reachability, cycle detection, and backtracking; switch to Dijkstra’s algorithm once edges carry different weights.