About Breadth-First Search
BFS explores all neighbors of the current node before moving to the next level. It uses a FIFO queue and guarantees the shortest path (minimum edges) in unweighted graphs.
Complexity Analysis
- Time Complexity
- O(V + E)
- Space Complexity
- O(V)
- Difficulty
- intermediate
Key Concepts
Level-by-Level Exploration
BFS visits all nodes at distance d before any at distance d+1. This is guaranteed by the FIFO queue.
Shortest Path (Unweighted)
The first time BFS reaches a node, it found the shortest path (fewest edges). This does NOT apply to weighted graphs — use Dijkstra for those.
Queue (FIFO)
The queue ensures first-in-first-out order, which is what makes BFS explore level by level rather than depth-first.
Common Pitfalls
Not for weighted graphs
BFS finds the shortest path only in UNWEIGHTED graphs. For weighted graphs, use Dijkstra's algorithm.
Memory usage
BFS can use a lot of memory because it stores all nodes at the current level in the queue. For very wide graphs, this can be a problem.