What is BFS?
BFS (Breadth-First Search) is a graph traversal algorithm that explores nodes level by level, starting from the closest neighbors before moving to farther ones.
Imagine dropping a stone into water — the ripples spread outward in concentric circles. BFS works the same way: it visits all nodes at distance 1, then distance 2, then distance 3, and so on.
Why Does It Matter?
BFS is a foundational graph algorithm and one of the most common topics in coding interviews.
- •Guarantees shortest path: Finds the shortest path in unweighted graphs
- •Level-order traversal: Used for tree level traversal and network layer exploration
- •Interview essential: Maze problems, flood fill, minimum moves — BFS is everywhere
How It Works
BFS uses a Queue data structure.
Step 1. Enqueue the starting node and mark it as visited.
Step 2. Dequeue a node from the front of the queue.
Step 3. Enqueue all unvisited neighbors of the dequeued node and mark them as visited.
Step 4. Repeat steps 2-3 until the queue is empty.
Time and Space Complexity
| Complexity | |
|---|---|
| Time | O(V + E) |
| Space | O(V) |
V is the number of vertices, E is the number of edges. Every node is visited once and every edge is checked once, giving O(V + E).
BFS vs DFS
| Comparison | BFS | DFS |
|---|---|---|
| Data Structure | Queue | Stack / Recursion |
| Traversal Order | Nearest first | Deepest first |
| Shortest Path | Guaranteed (unweighted) | Not guaranteed |
| Memory | Higher for wide graphs | Higher for deep graphs |
| Use Cases | Shortest distance, level traversal | Path finding, cycle detection |
Use BFS when you need the shortest path. Use DFS when you need to explore all possible paths.
Classic BFS Problems
Maze Solving — Find the minimum number of moves from start to end. With BFS, the first time you reach the destination is the shortest path.
Multi-source BFS — Start BFS simultaneously from multiple sources (e.g., "rotting oranges"). Enqueue all starting points first, then process normally.
Network Connectivity — Determine whether two nodes belong to the same connected component.
Common Mistakes
- •Marking nodes as visited when dequeuing instead of when enqueuing leads to duplicate entries in the queue
- •Missing boundary checks in 2D grid problems causes index out-of-bounds errors
- •Forgetting to enqueue all starting points in multi-source BFS
See It in Action on AlgoNote
Watch BFS spread across a graph like ripples on water, step by step on AlgoNote. Build your own graph, configure the edges, and observe the traversal process in real time.