Depth-first search
Not met yet
Depth-first search follows each road as far as it goes before trying the next, and only goes back when there's nowhere new to go. The simplest way to write it is a function that notes a place, then calls itself for each neighbour not yet reached; the calls waiting underneath remember where to come back to. A stack does the same job without recursion. DFS reaches everything it can, but the first route it finds to a place is often not the shortest. Use it for "can I get there at all", for trying every route, and for puzzles.
Try it
main.pyOutput
Press Run and what your program prints shows up here.
Easy to get wrong
- Thinks depth-first search reaches places nearest first.
- Thinks depth-first search stops at the first dead end, rather than going back and trying the next road.
- Thinks depth-first search on two-way roads goes round in circles forever, even when it skips places already reached.
- Thinks the first route depth-first search finds to a place is the shortest one.