Introduction to BFS
Breadth-First Search is a graph traversal algorithm that explores nodes level by level in a tree or a graph.
This makes BFS extremely useful for problems like:
- Finding the shortest path in an unweighted graph.
- Printing a tree level by level.
- Identifying connected components in an undirected graph.
- or Finding the shortest transformation sequence from one word to another.
It is also one of the most common patterns in coding interviews.
In this chapter, I’ll break down:
- what BFS is
- how it works
- how to implement it in code
What is Breadth First Search?
BFS is a graph traversal algorithm that explore nodes level by level.
Unlike DFS, which dives deep along one path, BFS visits all nodes at the current depth before moving to the next.
Think of BFS like ripples in a pond:
- When you throw a stone into a pond, the ripples spread evenly outward in all directions.
- BFS does the same: it visits all immediate neighbors first, then their neighbors, and so on.
BFS applies to any structure that can be represented as a set of nodes and edges like trees, tries, graphs and 2D grids.
Let’s see how BFS traverses this graph:
- We start from node 1
- Next, we visit all neighbors of 1: 2 and 3.
- In the next iteration, visit neighbors of 2 and 3 that are unvisited: 4 and 5
- Since there is no next level, our traversal is complete.
Final BFS traversal order is: 1, 2, 3, 4, 5
How to Implement BFS?
Now that you know what BFS is, lets see how to implement it in code.
To implement BFS, we use queue data structure.
Here’s a generic approach to solve BFS problems:
- Initialize an empty queue
- Initialize a
visitedset or array to avoid revisiting nodes - Enqueue the starting node to the queue and mark it as visited
- While the queue is not empty:
- Dequeue a node and process it.
- For each of its neighbors:
- If not visited, enqueue and mark visited
- Continue until the queue is empty
The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges in the graph.
This is because each node is processed once when it is dequeued and each edge is examined at most twice in an undirected graph (once from each endpoint) and exactly once in a directed graph.
The space complexity of BFS is O(V) since, in the worst case, the queue and visited set can store up to V nodes.
In some BFS-related problems, you may have multiple starting nodes instead of just one. These are called multi-source BFS problems.
The only change compared to standard BFS is that we enqueue all starting nodes at the beginning and mark them as visited. Then run BFS as usual.