Uninformed Search: BFS, DFS, and Iterative Deepening
Why this matters
A delivery robot starts in the lobby of a small building and has to reach the mail room. It knows which rooms are joined by corridors but has no sense of distance or direction, so all it can do is try corridors in a systematic order. That order decides whether it finds the shortest route, how much it must remember on the way, and whether it ever stops at all.
The idea
The frontier is the collection of nodes that have been generated but not yet expanded.
Breadth-first search (BFS) keeps the frontier in a first-in, first-out queue, so it expands every node at depth k before any node at depth k + 1. It keeps a reached set of every state already generated and never generates a state twice. Because the first path BFS finds to any state is a shallowest one, it can goal-test each node the moment it is generated, and it returns a path with the fewest actions.
Depth-first search (DFS) keeps the frontier in a last-in, first-out stack, so it always expands the deepest node, diving down one branch and backing up only at a dead end. It goal-tests a node when it pops it and returns the first goal it reaches, which need not be the shallowest.
Worked example
The robot's building has seven rooms, from S (the lobby, the start) to G (the mail room, the goal), joined by eight two-way corridors.
The conventions for every run: successors are generated in alphabetical order; DFS pushes them in reverse, so the alphabetically first one lands on top of the stack and is popped first; frontier size is counted at the start and after each expansion; time is counted as the number of goal tests.
Try it yourself
Run BFS from S on the corridor graph with goal E instead of G, using the lesson's conventions. List the states in the order they are goal-tested, and give the largest frontier size.
The order is S, A, B, C, D, G, E, seven goal tests, and the largest frontier is 3 (B, C, D after expanding A, then C, D, G after expanding B). E is tested when it is generated during the expansion of C, and BFS returns S → A → C → E.










