Breadth-first search
BFS explores in the opposite order: visit everything 1 step away, then everything 2 steps away, expanding like a ripple. The tool that enforces this order is a queue (first in, first out, from Data Structures) instead of DFS's stack.
The payoff is the property interviews test constantly:
BFS reaches every node by a shortest possible route (fewest edges).
So "shortest path" in a maze, word ladder, or social network, where every step costs the same, means BFS. The loop: pop a node, push its unvisited neighbors with distance + 1, repeat. Same O(V + E) cost as DFS, same visited-set rule.
Code exercise · python
Run this. A grid is a graph in disguise: cells are nodes, and each open cell (0) connects to its 4 open neighbors. Walls are 1. The deque from Data Structures gives O(1) pops from the left.
Quiz
When must you choose BFS over DFS?
Code exercise · python
Your turn, the most famous grid problem: count the islands. 1 is land, 0 is water, and land cells connect up/down/left/right. Like count_components in lesson 7-1: scan every cell, and each un-seen land cell starts a flood (sink) that marks its whole island.
Problem
You need the smallest number of moves for a knight to get from one square to another on a chessboard, where every move counts as 1. Which traversal do you use, BFS or DFS?