Graphs
Retrieval: which traversal, which structure?
Two problems rebuilt cold, plus the decisions that pick the approach.
Key idea
Pick by what the question measures
Depth-first is shorter to write and fine whenever the question is about membership or structure rather than distance. Breadth-first is required when the answer is a shortest count of steps.
| Question | Approach |
|---|---|
| Which cells form a region, how big is it | either, depth-first is shorter |
| Fewest steps to reach something | breadth-first |
| Distance from the nearest of many starts | breadth-first seeded with all of them |
| Can everything be ordered given constraints | topological, count what came out |
| Are these two joined, with edges arriving over time | union-find |
| How many separate groups on a fixed graph | either traversal or union-find |
Tip
And one habit
If a solution needs a search from every node, check whether the question can be reversed and answered by one search from the destinations. That reversal turned two problems in this unit from quadratic to linear.
Which approach fits?
Friendships are added one at a time, and after each addition you must report whether two specific people are now connected. Which approach fits best?
Rotting Oranges, from scratch
You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.
N-Queens, from scratch
You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.