Breadth-First Search
Overview
Breadth-First Search (BFS) is a fundamental algorithm for traversing Graphs and Trees. Instead of plunging deep down a single path, it explores the data structure level by level. Starting at a specific origin node, it visits all immediate neighbors first, then it visits all the neighbors' neighbors, and so on, radiating outward like a ripple in a pond.
The defining characteristic of BFS is its use of a Queue (First-In-First-Out data structure). This ensures that nodes discovered earlier (closer to the start) are processed before nodes discovered later.
Because of this strict radial expansion, BFS is the absolute gold standard for finding the Shortest Path in an unweighted graph (e.g., 'What is the minimum number of moves to escape a maze?'). If you need to find the closest item to your starting point, BFS guarantees that the first time you encounter the item, you have reached it via the shortest possible route.
Syntax
import java.util.*;
public class GraphBFS {
// Adjacency List graph representation
Map<Integer, List<Integer>> adjList = new HashMap<>();
public void bfs(int startNode) {
// 1. The Queue tracks what to process next in FIFO order
Queue<Integer> queue = new LinkedList<>();
// 2. The Visited Set prevents infinite loops in cyclic graphs
Set<Integer> visited = new HashSet<>();
// Setup start node
queue.offer(startNode);
visited.add(startNode); // ALWAYS mark visited as soon as you enqueue!
int distanceLevel = 0;
while (!queue.isEmpty()) {
int levelSize = queue.size(); // Lock in the size of the current level
// Process ALL nodes on the current level before moving deeper
for (int i = 0; i < levelSize; i++) {
int curr = queue.poll();
System.out.println("Processing Node " + curr + " at Distance " + distanceLevel);
// Add all unvisited neighbors to the queue
for (int neighbor : adjList.getOrDefault(curr, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
visited.add(neighbor); // Mark visited immediately!
queue.offer(neighbor);
}
}
}
distanceLevel++; // Moving one layer further away from the origin
}
}
}Common Pitfalls
- Marking nodes as visited when DEQUEUING instead of ENQUEUING. If you wait to mark a node visited until you
poll()it out of the queue, multiple different nodes currently processing on the same level might see it as 'unvisited' and enqueue duplicates of the same node, causing massive memory bloat and TLE errors. - Forgetting the Visited Set entirely. In a Tree, a visited set isn't needed because data only flows downward. In a Graph, cycles exist. If Node A connects to Node B, and Node B connects back to Node A, BFS without a visited set will bounce between A and B infinitely.
- Using a Stack instead of a Queue. If you accidentally instantiate a
Stackinstead of aLinkedListfor your Queue interface, your algorithm instantly transforms into a Depth-First Search (DFS) and entirely loses its 'shortest path' level-by-level properties.
Interview Questions
BFS processes nodes strictly by distance from the origin. It processes all nodes at distance 1, then all nodes at distance 2, etc. Therefore, the very first time BFS encounters a target node, it is mathematically proven to be via the shortest possible path. DFS dives deep randomly and might find a path of length 100 before backtracking and finding a path of length 2.
Time Complexity is O(V + E) where V is vertices and E is edges, because every node and every connected edge is processed at most once. Space Complexity is O(V) because in the worst-case (e.g., a star graph), the Queue and the Visited Set will need to store almost all V nodes simultaneously.
Real-World Example
Social Network 'Degrees of Separation'. When LinkedIn shows that someone is a '2nd connection' or '3rd connection', it runs a massive BFS starting from your profile. Level 1 (queue depth 1) contains your direct friends. Level 2 (queue depth 2) contains their friends. BFS instantly returns the shortest connection distance to any target user.
import java.util.*;
class User { String id; List<User> connections; }
public class LinkedInNetwork {
public int findDegreesOfSeparation(User me, User target) {
Queue<User> queue = new LinkedList<>();
Set<User> visited = new HashSet<>();
queue.offer(me);
visited.add(me);
int degrees = 0;
while(!queue.isEmpty()) {
int size = queue.size();
for(int i = 0; i < size; i++) {
User curr = queue.poll();
// We found the target user! Return the current depth level.
if (curr.id.equals(target.id)) return degrees;
for(User connection : curr.connections) {
if(visited.add(connection)) { // Set.add() returns true if the item is newly added
queue.offer(connection);
}
}
}
degrees++; // Increment degree of separation after processing the full level
}
return -1; // Users are completely unconnected in the graph
}
}Check Your Knowledge
Test your understanding of Breadth-First Search with these quick questions.