BFS
Explore in rings: everything one step away, then everything two steps away. Because the cells arrive in that order, the first time the search touches one, it has touched it by a shortest route.
Problems worked on this page, and more to practise
- 1926. Nearest Exit from Entrance in Maze
- 994. Rotting Oranges
- 127. Word Ladder
- 102. Binary Tree Level Order Traversal
- 199. Binary Tree Right Side View
- 1091. Shortest Path in Binary Matrix
- 542. 01 Matrix
- 1162. As Far from Land as Possible
- 286. Walls and Gates
- 752. Open the Lock
- 433. Minimum Genetic Mutation
- 279. Perfect Squares
- 815. Bus Routes
When should I use BFS instead of DFS?
When the question is “fewest steps” and every step costs the same. BFS reaches cells in order of distance, so the first time it touches one it has touched it by a shortest route. DFS reaches the same cells but in no useful order, so the first route it finds to a cell is usually not the shortest and you would have to try them all. When the question is “is there any route” or “how many separate pieces”, either search works and DFS is often shorter to write.
Why do you mark a cell visited when it enters the queue, not when it leaves?
Because between going in and coming out, a cell is already spoken for. If you only mark it on the way out, every neighbour that looks at it in the meantime queues it again, so one cell can enter the queue once per neighbour. The answer still comes out right, but the queue grows several times larger than it needs to be. Marking on the way in keeps the total number of queue entries at one per cell, which is what makes the cost O(V + E).
Why use collections.deque instead of a list?
A list stores its items in one block, so removing the first item shifts every remaining item down by one. That is O(n) per removal, and doing it once per cell turns a linear scan into a quadratic one. A deque is built from linked blocks and pops from either end in constant time. Use append and popleft, and never list.pop(0).
What is multi-source BFS?
Ordinary BFS with more than one starting cell in the queue before the first pop. Every source sits at distance 0, so the first ring is everything one step from any source, the second is everything two steps from any source, and so on. It answers questions like “how long until every orange has rotted”, where the spread starts in several places at once. Think of it as one invisible cell joined to all the sources: the rings are measured from that.
Does BFS find the cheapest path when the steps have different costs?
No. BFS counts edges, not cost, so it returns the route with the fewest steps even when a longer route is cheaper. With arbitrary non-negative weights you need Dijkstra, which pops the cheapest node so far from a heap instead of the oldest from a queue. There is one case in between: when every edge costs 0 or 1, 0-1 BFS keeps a deque and pushes zero-cost moves to the front and one-cost moves to the back.