The queue and the stack get their job
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 9 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.
The lesson climbs in steps
You write more in this lesson than in any before it: two searches, components, degrees and a second representation. So it is climbed one rung at a time rather than in one leap:
- Watch. A graph of eight nodes, both searches run on it, every step in a table. You write nothing.
- Fill the holes. BFS arrives with its loops written; two lines are missing.
- Write it yourself. DFS, recursive DFS, components, degrees and the adjacency matrix — empty skeletons, and the test says whether you got them right.
- Measure. The same code on a network of a thousand books.
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 6 measures it, and the number is probably larger than you will want to write.