In lesson 4 you built a queue and a stack. In lesson 5 you showed that recursion and an explicit stack are the same algorithm.

Both lessons ended on a promise. Lesson 4's:

Swap the queue for a stack and you get depth-first search — a correct program answering a different question. You will build both in lesson 14.

This is that lesson. And here the queue and the stack do not illustrate anything — they work.

The graph you will search

Your library's "readers also borrowed" network: a node is a book, and an edge joins two books somebody borrowed one after the other.

The shape of such a network is not arbitrary. A reader borrows a run of books, so every borrowing trail is a chain; junctions appear only where two readers happened to pick the same book.

Long chains, rare junctions — the same shape as a public transport network. Which is why transit in step 8 is a comparison rather than an analogy.

The only difference between the two searches

BFS and DFS are the same program. Both keep a collection of nodes not yet visited, both take one out at a time, both put the neighbours back in.

One thing differs: which end they take from.

	takes from	which is
BFS	the front	a queue (lesson 4)
DFS	the back	a stack (lesson 4)

Two lines of code. And because of them the two answer different questions.

Guess before you read on

Both searches find a path if one exists. Both are correct.

Will the path DFS finds be as short as the one BFS finds? And if not, how much longer: a few percent, a few times over, or something else?

Write your answer down. Step 5 measures it, and the number is probably larger than you will want to write.