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

Quick check· 5 min

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?

Union-find, merging on each addition and comparing roots to answerRebuild the adjacency map and run a breadth-first search after each additionDepth-first search from one person after each additionTopological sort, since the additions impose an order

Problem· 18 min

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.

Problem· 30 min

N-Queens, from scratch

Graphs

115 / 170

GraphsLesson 8 of 8About 58 min

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

Quick check· 5 min

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?

Problem· 18 min

Rotting Oranges, from scratch

Problem· 30 min