The other traversal
BFS answers "fewest hops", but many graph questions never mention distance: can this task's dependencies be satisfied at all? Which users form one cluster of linked accounts? Which pixels belong to this connected region? (that last one is the flood fill behind every paint-bucket tool). For reachability questions, visiting order does not matter — only coverage does — and that opens the door to BFS's sibling.
Depth-first search (DFS) is the lesson 5-3 exploration loop with exactly one change: the frontier is a stack instead of a queue. pop() hands you the newest discovery, so instead of finishing ring 1 before ring 2, the search plunges down one path as far as it can, then backtracks to the most recent junction with unexplored exits. The 5-3 quiz warned that this destroys BFS's shortest-path guarantee — for pure reachability there is nothing to destroy.
Everything else survives unchanged: the seen set still prevents infinite loops around cycles, every node and edge is still touched at most once, and the cost is still O(nodes + edges).
Code exercise · python
Run this. Same friend network as lesson 5-3, same loop, and the ONLY difference between the two functions is popleft (oldest) versus pop (newest). BFS radiates outward ring by ring; DFS dives you → ben → dee → eli before ever touching ana's branch. Both visit all six people.
Quiz
DFS is often written recursively instead: `visit(node)` marks the node seen, then calls itself on each unseen neighbor — no frontier list anywhere. Where did the stack go?
Counting the islands
A traversal from one start visits everything reachable from it — its connected component. Real graphs are often several disconnected clusters, and "how many clusters?" is itself the product: fraud teams cluster linked accounts, image tools count distinct regions, network tools flag machines cut off from the rest.
The algorithm needs no new machinery, just an outer loop:
- Keep one
seenset for the whole graph and a counter at 0. - Walk over every node. If it is already seen, skip it.
- If not, you have discovered a brand-new component: count it, and run a traversal (DFS or BFS, either works — this is pure reachability) from that node to mark the whole component seen.
Each traversal swallows one entire cluster, so the counter increments exactly once per component. Total cost is still O(nodes + edges): the outer loop touches each node once, and the traversals collectively touch each edge once.
Code exercise · python
Your turn: implement `component_count(adj)` with the outer-loop pattern. One shared `seen` set; for every unseen node, add 1 to the count and DFS from it (explicit stack) marking everything reachable. The network below has three clusters: {ana, ben}, {cai, dee, eli}, and fay alone.
Quiz
Two tasks: (A) "fewest introductions between two people" and (B) "are these two servers connected at all?". Which traversal does each need?