Breadth-First Search

Breadth-first search (BFS) is a graph traversal algorithm that visits every node at the current distance from a starting node before moving to nodes farther away. It processes a graph in layers, using a queue to control the order of visits. BFS guarantees the shortest path between two nodes when every edge has equal weight.

This guide covers how BFS works, when to use it instead of depth-first search (DFS), how to calculate its time and space complexity, and which implementation mistakes cause it to fail in production code.

What Is Breadth-First Search?

Breadth-first search is an algorithm that explores a graph or tree level by level, visiting all neighbors of a node before visiting any node farther away, using a first-in-first-out (FIFO) queue to track which node to process next.

BFS starts at a single source node. It marks that node as visited and adds it to a queue. It then removes the node at the front of the queue, examines its unvisited neighbors, marks each of them as visited, and adds them to the back of the queue. This process repeats until the queue is empty.

Three components define BFS:

Component	Function
Queue	Stores discovered nodes in the order they are found (FIFO)
Visited set	Tracks which nodes have already been processed to prevent repeat visits
Adjacency structure	Stores which nodes connect to which (adjacency list or adjacency matrix)

BFS differs from depth-first search in traversal order. DFS follows one path as deep as possible before backtracking. BFS expands outward in rings around the source node, one distance level at a time.

How BFS Works, Step by Step

BFS follows five fixed steps for every traversal:

1. Add the source node to the queue and mark it as visited.
2. Remove the node at the front of the queue.
3. Check every neighbor of that node.
4. Mark each unvisited neighbor as visited and add it to the back of the queue.
5. Repeat steps 2 through 4 until the queue is empty.

A node enters the visited state the moment it is discovered and added to the queue. It enters the processed state when it reaches the front of the queue and its neighbors are examined. Marking a node as visited at discovery time, not at processing time, prevents the same node from being added to the queue more than once.

A Worked Example, Node by Node

Consider a graph with six nodes: A, B, C, D, E, and F. Node A connects to B and C. Node B connects to A, D, and E. Node C connects to A and F. Nodes D, E, and F have no further unvisited connections.

Step	Action	Queue After Step	Visited Set	Order So Far
1	Add A	[A]	{A}	[]
2	Dequeue A, add B and C	[B, C]	{A, B, C}	[A]
3	Dequeue B, add D and E	[C, D, E]	{A, B, C, D, E}	[A, B]
4	Dequeue C, add F	[D, E, F]	{A, B, C, D, E, F}	[A, B, C]
5	Dequeue D, no new neighbors	[E, F]	{A, B, C, D, E, F}	[A, B, C, D]
6	Dequeue E, no new neighbors	[F]	{A, B, C, D, E, F}	[A, B, C, D, E]
7	Dequeue F, no new neighbors	[]	{A, B, C, D, E, F}	[A, B, C, D, E, F]

The traversal order is A, B, C, D, E, F. The queue becomes empty after step 7, which ends the algorithm.

The following Python implementation performs the same traversal using a dictionary for the adjacency list and collections.deque for the queue:

python

from collections import deque

def bfs(graph, start):

    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": ["C"]

}

print(bfs(graph, "A"))

# Output: ['A', 'B', 'C', 'D', 'E', 'F']

BFS vs. DFS: How Do You Know Which One to Use?

BFS and DFS solve different problems because they explore graphs in different orders.

Factor	Breadth-First Search	Depth-First Search
Traversal order	Level by level, outward from the source	Deep along one path before backtracking
Data structure	Queue (FIFO)	Stack (LIFO) or recursion
Shortest path (unweighted)	Guaranteed	Not guaranteed
Memory use pattern	Grows with the widest level of the graph	Grows with the deepest path in the graph
Typical use case	Shortest path, nearest-neighbor search, level-order problems	Cycle detection, topological sorting, exhaustive path search

Use BFS when the goal is the shortest path in an unweighted graph, when the target is close to the source, or when the problem specifies “minimum number of steps” or “fewest connections.” Use DFS when the goal is to explore every possible path, when memory is limited in a graph with many wide levels, or when the problem requires backtracking, such as maze generation or constraint satisfaction.

If the graph has weighted edges, neither BFS nor DFS finds the shortest path by default. Dijkstra’s algorithm, which replaces the FIFO queue with a priority queue, finds the shortest path when edge weights differ.

BFS Time and Space Complexity

BFS runs in O(V + E) time and uses O(V) space, where V is the number of vertices and E is the number of edges in the graph.

The time complexity comes from two facts. Every vertex is added to the queue exactly once, which accounts for O(V) operations. Every edge is examined exactly once, when the algorithm checks the neighbors of the vertex it belongs to, which accounts for O(E) operations. Adding these two costs together produces O(V + E).

A graph with 6 vertices and 7 edges requires at most 13 constant-time operations to complete a full BFS traversal: 6 for visiting each vertex and 7 for checking each edge.

Space complexity depends on two structures: the queue and the visited set. Both can hold up to V elements in the worst case, which produces O(V) auxiliary space. This space requirement does not depend on the number of edges.

The graph representation changes performance, though not the algorithm’s complexity class:

Representation	Neighbor Lookup Cost	Time Complexity	Space Complexity
Adjacency list	Visits only the actual neighbors of each vertex	O(V + E)	O(V + E)
Adjacency matrix	Scans a full row of V entries for each vertex	O(V²)	O(V²)

Adjacency lists produce faster BFS traversals on sparse graphs, where the number of edges is much smaller than V². This complexity analysis follows the standard proof format used in Cormen, Leiserson, Rivest, and Stein’s Introduction to Algorithms (MIT Press).

Common BFS Implementation Mistakes

Three mistakes account for most BFS bugs in production code.

1. Marking nodes as visited at dequeue time instead of enqueue time. This allows the same node to enter the queue multiple times before it is first processed, which wastes memory and can produce an incorrect traversal order. Mark a node as visited the moment it is added to the queue, not when it is removed.
2. Omitting the visited set entirely. Without a visited set, BFS can re-enter cycles in the graph and run indefinitely. Every BFS implementation on a graph with cycles requires a visited set or equivalent tracking mechanism.
3. Using a stack instead of a queue. A stack produces depth-first behavior, not breadth-first behavior, even when every other part of the code matches a standard BFS implementation. The queue’s FIFO order is what produces level-by-level traversal.

Applications of Breadth-First Search

BFS applies to problems that require finding the nearest reachable nodes from a starting point. Four categories cover most production use cases: shortest-path calculation, connectivity analysis, network exploration, and structural classification.

• Shortest path in an unweighted graph. BFS finds the minimum number of edges between two nodes, which applies to maze solving, minimum-move puzzle solving, and routing problems where every step has equal cost.
• Connected components. BFS identifies every node reachable from a given starting node, which groups nodes into clusters. This applies to identifying isolated subnetworks or separate communities within a larger graph.
• Bipartite graph checking. BFS assigns alternating groups to nodes as it traverses the graph. If two adjacent nodes end up in the same group, the graph is not bipartite.
• Cycle detection. BFS detects a cycle in an undirected graph when it encounters an edge that connects two already-visited nodes that are not the current node’s immediate parent.

BFS in Coding Interviews

Coding interview problems signal a BFS solution through specific wording. The phrases “shortest path,” “minimum number of steps,” “fewest moves,” and “level order” indicate that BFS is the expected approach. Binary tree level-order traversal, word ladder problems, and minimum-knight-move problems on a chessboard are common BFS interview problems, because each one asks for the minimum number of steps between two states.

Real-World Systems Use Cases

• Web crawling. A crawler starting from a seed URL visits its outgoing links first, then expands to the next layer of linked pages, which mirrors BFS’s level-by-level exploration.
• Social network analysis. BFS calculates degrees of separation by finding the shortest connection path between two users, starting with direct connections before expanding to second-degree and third-degree connections.
• Network broadcasting. BFS models how a message propagates outward through a connected network, reaching the closest nodes first.
• Dependency and blast-radius analysis. Starting from a compromised system or a changed component, BFS identifies directly connected systems first, then expands to second- and third-hop dependencies, which supports prioritizing which systems require review first.

BFS Variants Worth Knowing

Two variants extend standard BFS to specific search conditions.

Bidirectional BFS runs two simultaneous searches, one from the source node and one from the target node, and stops when the two searches meet. This reduces the number of nodes explored from O(b^d) to approximately O(b^(d/2)) in a graph with branching factor b and solution depth d, which produces a significant reduction in explored states for large graphs with a known target.

Multi-source BFS starts from several source nodes at the same time instead of one, adding all sources to the queue at the start of the traversal. This finds the shortest distance from any node to its nearest source, which applies to problems like finding the nearest hospital, server, or resource location across a network. Dijkstra’s algorithm extends this same queue-based approach to graphs with weighted edges, replacing the FIFO queue with a priority queue ordered by total path cost.

Advantages and Disadvantages of BFS

Advantages	Disadvantages
Guarantees the shortest path in unweighted graphs	Uses more memory than DFS on graphs with wide levels
Simple to implement with a queue and a visited set	Does not guarantee the shortest path on weighted graphs
Explores every node at each level without omission	Explores many nearby nodes even when the target lies far along a single path
Supports parallel execution, since nodes at the same level can be processed simultaneously	Requires storing the entire current frontier in memory

Where BFS Came From

Computer scientist Edward F. Moore first published the breadth-first search algorithm in 1959, in a paper titled “The Shortest Path Through a Maze,” presented at the International Symposium on the Theory of Switching. Electrical engineer C.Y. Lee independently developed a similar algorithm for wire routing in circuit design during the same period. Both applications relied on the same core principle: exploring a search space outward in layers to guarantee the shortest connection between two points.

Frequently Asked Questions

The Bottom Line

BFS answers one specific question well: what is the shortest path, measured in number of edges, from a starting node to every other reachable node in the graph. Choosing BFS over DFS, Dijkstra’s algorithm, or another traversal method depends on whether the graph is weighted, whether the target is known in advance, and whether the goal is the shortest path or complete exploration. Applying the queue-based, level-by-level structure correctly, with a visited set that marks nodes at discovery time, prevents the majority of implementation errors that occur in practice.