A lesson from the data structures and algorithms bootcamp. About a 12 minute read.
These are not two algorithms. They are one algorithm with two different containers, and everything that distinguishes them follows from that one substitution. Getting that straight is worth more than memorising both, because it means you can derive either from the other and you can see immediately why Dijkstra is the same code again with a third container.
Put the start node in a container. While the container is not empty, take something out, mark it, and put its unvisited neighbours in. That is the entire skeleton, and it does not care what the container is. A STACK gives you depth-first: the most recently discovered node comes out next, so you plunge down one branch to the end before backing up. A QUEUE gives you breadth-first: the earliest discovered node comes out next, so you finish everything one step away before looking at anything two steps away. A PRIORITY QUEUE gives you Dijkstra, where the cheapest-so-far node comes out next. Three famous algorithms, one loop, and the only difference is what 'next' means.
The rest of this lesson continues with 5 further sections. See the full curriculum.
Browse all 536 practice puzzles