Topic 64 of 78
Breadth-First Search
Overview
Breadth-First Search (BFS) is an algorithm used to traverse or search a Graph or Tree. Instead of diving deep into the graph, BFS explores the graph uniformly in 'layers' or 'concentric circles'. It checks all immediate neighbors first, before moving to the neighbors' neighbors. Because it radiates outward evenly, BFS guarantees that the first time you reach a destination node, you have found the absolute shortest path (in an unweighted graph).
Syntax
The Queue ensures that we process nodes in the exact order we discover them (FIFO), which enforces the 'layer-by-layer' exploration.
BFS using a Queue
java
public void bfs(Map<Integer, List<Integer>> graph, int startNode) {
// 1. BFS ALWAYS requires a Queue
Queue<Integer> queue = new LinkedList<>();
// 2. Graphs can have cycles, so we MUST track visited nodes!
Set<Integer> visited = new HashSet<>();
// Initialize
queue.offer(startNode);
visited.add(startNode);
while (!queue.isEmpty()) {
int current = queue.poll();
System.out.println("Visited: " + current);
// Check all neighbors
for (int neighbor : graph.getOrDefault(current, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
visited.add(neighbor); // Mark visited immediately
queue.offer(neighbor); // Add to queue for next layer
}
}
}
}Common Pitfalls
- Forgetting the `visited` HashSet. Trees don't strictly need a visited set because they flow down, but Graphs have cycles. Without a visited set, your BFS will run in an infinite loop.
- Trying to use a Stack instead of a Queue. Using a Stack fundamentally changes the algorithm into Depth-First Search (DFS).
Interview Tips
- BFS radiates outward in concentric circles. In an unweighted graph, the first time you reach the target node, you have found the guaranteed shortest path.
Real-World Example
Social networks use BFS to find 'Degrees of Separation' (e.g., finding out that you are a 3rd-degree connection to someone on LinkedIn).
example
java
public int getDegreesOfSeparation(int startUser, int targetUser) {
Queue<Integer> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
int degree = 0; // Tracks the BFS layers
queue.offer(startUser);
visited.add(startUser);
while (!queue.isEmpty()) {
int layerSize = queue.size();
// Process entire layer at once
for (int i = 0; i < layerSize; i++) {
int current = queue.poll();
if (current == targetUser) return degree;
for (int friend : database.getFriends(current)) {
if (visited.add(friend)) { // .add() returns true if new
queue.offer(friend);
}
}
}
degree++; // We just finished a full layer, increment degree!
}
return -1; // No connection found
}