Breadth-First Search (BFS) Algorithm: Comprehensive Explanation and Implementation
Introduction
When I first started exploring graph algorithms, Breadth-First Search was one of the earliest ones I got comfortable with, and I still think it’s the right place to start. BFS is a traversal algorithm that explores a graph layer by layer, starting from a source vertex and visiting every vertex at distance 1 before moving on to distance 2, then distance 3, and so on. This “wave-like” expansion is what makes BFS so useful: it naturally finds the shortest path (in terms of number of edges) from a source to every other reachable vertex in an unweighted graph.
I use BFS whenever I need to answer questions like “what’s the minimum number of steps to get from A to B” or “which nodes are reachable within k hops.” It shows up everywhere from network broadcasting to social network analysis to solving sliding puzzle games.
History and Background
BFS doesn’t have a single flashy origin story the way some named algorithms do. It emerged from early work in graph theory and maze-solving procedures. The technique is often traced back to Konrad Zuse in the late 1940s, who described a maze-solving algorithm using breadth-first principles in his (at the time unpublished) work on the Plankalkül programming language. It was independently rediscovered by Edward F. Moore in 1959, who used it to find the shortest path out of a maze, and by C. Y. Lee in 1961 in the context of wire routing for circuit design (which is why some older texts call it “Lee’s algorithm”). Over time, BFS became a standard building block taught alongside DFS in every algorithms curriculum, formalized in the classic treatment by Cormen, Leiserson, Rivest, and Stein (CLRS) in Introduction to Algorithms.
Problem Statement
Given a graph G = (V, E) and a source vertex s, I want to visit every vertex reachable from s in order of increasing distance (number of edges) from s, and typically I also want to record that distance and a way to reconstruct the shortest path to each vertex.
Core Concepts
- Vertex (Node): A fundamental unit of the graph.
- Edge: A connection between two vertices, which may be directed or undirected.
- Frontier: The set of vertices currently being expanded at a given “layer.”
- Visited set: Vertices I’ve already discovered, so I don’t process them twice.
- Queue (FIFO): The data structure that enforces the layer-by-layer order — vertices are processed in the exact order they were discovered.
- Distance array: Stores the number of edges from the source to each vertex.
- Predecessor array: Stores the vertex from which each vertex was first discovered, used to reconstruct shortest paths.
How It Works
- Start at the source vertex, mark it visited, and set its distance to 0.
- Push the source into a queue.
- While the queue is not empty, pop the front vertex u.
- For every neighbor v of u that hasn’t been visited yet, mark v visited, set its distance to distance[u] + 1, set its predecessor to u, and push v into the queue.
- Repeat until the queue is empty.
Because I always add new vertices to the back of the queue and always process from the front, vertices are guaranteed to be processed in non-decreasing order of distance from the source.
Working Principle
The key insight behind BFS is that a FIFO queue enforces strict ordering by discovery time, and discovery time corresponds exactly to shortest distance in an unweighted graph. Every vertex at distance d gets fully expanded (all its neighbors examined) before any vertex at distance d+1 is expanded. This is what guarantees correctness: by the time I pop a vertex u with distance d, I know for certain that d is the shortest possible distance to u, because any shorter path would have already caused u to be discovered earlier.
Mathematical Foundation
For an unweighted graph, the distance function computed by BFS satisfies:
$$\delta(s, v) = \min { , |P| : P \text{ is a path from } s \text{ to } v , }$$
where |P| is the number of edges in path P. BFS computes this exactly, and it can be proven inductively: assume all vertices at distance ≤ d have correct distance labels; then any vertex v at true distance d+1 must have at least one neighbor at distance d (otherwise its distance would not be d+1), and that neighbor will discover v during its expansion, correctly labeling it d+1.
The total work done is bounded by:
$$T(V, E) = O(V + E)$$
since every vertex is enqueued once, and every edge is examined at most once (or twice for undirected graphs, once per direction).
Diagrams
flowchart TD
A[Start: enqueue source, mark visited] --> B{Queue empty?}
B -- No --> C[Dequeue vertex u]
C --> D[For each neighbor v of u]
D --> E{v visited?}
E -- No --> F[Mark v visited, set distance, enqueue v]
E -- Yes --> D
F --> D
D --> B
B -- Yes --> G[Done]
Pseudocode
BFS(G, s):
for each vertex v in G.V:
visited[v] = false
distance[v] = infinity
predecessor[v] = NIL
visited[s] = true
distance[s] = 0
Q = empty queue
enqueue(Q, s)
while Q is not empty:
u = dequeue(Q)
for each v in G.adj[u]:
if visited[v] == false:
visited[v] = true
distance[v] = distance[u] + 1
predecessor[v] = u
enqueue(Q, v)
Step-by-Step Example
Suppose I have this undirected graph:
1 - 2
1 - 3
2 - 4
3 - 4
4 - 5
Starting BFS from vertex 1:
- Visit 1, distance 0. Queue: [1]
- Dequeue 1. Neighbors 2, 3 are unvisited → distance 1. Queue: [2, 3]
- Dequeue 2. Neighbor 4 is unvisited → distance 2. Queue: [3, 4]
- Dequeue 3. Neighbor 4 already visited, skip. Queue: [4]
- Dequeue 4. Neighbor 5 unvisited → distance 3. Queue: [5]
- Dequeue 5. No unvisited neighbors. Queue: []
Final distances: 1→0, 2→1, 3→1, 4→2, 5→3.
Time Complexity
- Best, Average, and Worst Case: O(V + E) for adjacency list representation, because every vertex is enqueued exactly once and every edge is examined a constant number of times.
- If I use an adjacency matrix instead, it becomes O(V²), since checking all neighbors of a vertex requires scanning an entire row regardless of how many actual edges exist.
Space Complexity
- O(V) for the visited array, distance array, predecessor array, and the queue itself in the worst case (a graph shaped like a star can have almost all vertices in the queue at once).
- If I’m using an adjacency list, that itself takes O(V + E) space, which I usually count separately as the graph’s storage cost rather than the algorithm’s auxiliary cost.
Correctness Analysis
I can prove BFS correctness formally using the loop invariant that at the start of each iteration, the queue contains vertices with distances that are non-decreasing and span at most two consecutive distance values. Combined with the inductive argument in the Mathematical Foundation section, this guarantees that when a vertex is dequeued, its recorded distance is indeed the shortest possible distance from the source. Since every reachable vertex is eventually enqueued (because BFS explores all edges from every dequeued vertex), completeness also holds — every reachable vertex will be visited.
Advantages
- Guarantees shortest paths in unweighted graphs.
- Simple to implement and reason about.
- Naturally supports level-order processing, which is useful in many applications beyond pure shortest paths.
- Predictable O(V + E) performance.
Disadvantages
- Doesn’t work correctly for weighted graphs unless all weights are equal.
- Can use significant memory for wide graphs, since the entire frontier may need to be stored at once.
- Not memory-efficient for very deep, narrow search spaces compared to DFS, which uses less memory in such cases.
Applications
- Shortest path computation in unweighted networks, such as hop-count routing.
- Web crawling, where I explore pages link by link outward from a seed page.
- Social network analysis, like finding “degrees of separation” between two people.
- Broadcasting and peer discovery in computer networks.
- Solving puzzles like the sliding tile puzzle or Rubik’s Cube where each move has equal cost.
- Finding connected components in a graph.
- Bipartite graph checking, by trying to 2-color vertices layer by layer.
Implementation in C
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
typedef struct {
int adj[MAX_VERTICES][MAX_VERTICES]; /* adjacency matrix */
int numVertices;
} Graph;
void initGraph(Graph *g, int n) {
g->numVertices = n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
g->adj[i][j] = 0;
}
void addEdge(Graph *g, int u, int v) {
g->adj[u][v] = 1;
g->adj[v][u] = 1; /* remove this line for a directed graph */
}
void bfs(Graph *g, int source) {
int visited[MAX_VERTICES] = {0};
int distance[MAX_VERTICES];
int predecessor[MAX_VERTICES];
int queue[MAX_VERTICES];
int front = 0, rear = 0;
for (int i = 0; i < g->numVertices; i++) {
distance[i] = -1;
predecessor[i] = -1;
}
visited[source] = 1;
distance[source] = 0;
queue[rear++] = source;
while (front < rear) {
int u = queue[front++];
printf("Visited: %d\n", u);
for (int v = 0; v < g->numVertices; v++) {
if (g->adj[u][v] == 1 && !visited[v]) {
visited[v] = 1;
distance[v] = distance[u] + 1;
predecessor[v] = u;
queue[rear++] = v;
}
}
}
printf("\nVertex\tDistance\tPredecessor\n");
for (int i = 0; i < g->numVertices; i++)
printf("%d\t%d\t\t%d\n", i, distance[i], predecessor[i]);
}
int main(void) {
Graph g;
initGraph(&g, 5); /* vertices 0..4, matching 1..5 from the example, zero-indexed */
addEdge(&g, 0, 1);
addEdge(&g, 0, 2);
addEdge(&g, 1, 3);
addEdge(&g, 2, 3);
addEdge(&g, 3, 4);
bfs(&g, 0);
return 0;
}
Sample Input and Output
Input: Graph with edges (0,1), (0,2), (1,3), (2,3), (3,4); source = 0.
Output:
Visited: 0
Visited: 1
Visited: 2
Visited: 3
Visited: 4
Vertex Distance Predecessor
0 0 -1
1 1 0
2 1 0
3 2 1
4 3 3
Optimization Techniques
- Adjacency list instead of matrix: Switching from O(V²) to O(V + E) traversal cost is the single biggest optimization for sparse graphs.
- Bidirectional BFS: When I know both the source and the target, running BFS simultaneously from both ends and stopping when the frontiers meet can dramatically cut down the search space, especially in large graphs like social networks.
- Bitset-based visited tracking: Using bitsets instead of boolean arrays reduces memory footprint and can speed up cache performance for very large graphs.
- 0-1 BFS (deque-based): When edge weights are only 0 or 1, I can use a deque instead of a plain queue to still get O(V + E) performance for this special weighted case.
Common Mistakes
- Forgetting to mark a vertex as visited at the time it’s enqueued rather than when it’s dequeued — this can cause the same vertex to be added to the queue multiple times.
- Using DFS logic (a stack) by mistake instead of a proper FIFO queue, which breaks the level-order guarantee.
- Not initializing the visited array between multiple BFS calls (for example, when finding connected components).
- Assuming BFS gives shortest paths on weighted graphs — it only works when every edge has equal weight.
- Off-by-one errors in distance calculation, especially forgetting to set the source’s distance to 0 explicitly.
Further Reading
- Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms, 3rd/4th Edition, MIT Press: https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- MIT OpenCourseWare, 6.006 Introduction to Algorithms, BFS lecture notes: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
- GeeksforGeeks, Breadth First Search: https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/
- Moore, E. F. (1959). “The shortest path through a maze.” Proceedings of the International Symposium on the Theory of Switching.
- Visualgo, Graph Traversal visualization: https://visualgo.net/en/dfsbfs
