A lesson from the Algorithms & Patterns module of the bootcamp. About a 12 minute read.
These are not two algorithms. They are one algorithm with two different containers, and everything that separates them follows from that one swap. Getting that straight is worth more than memorizing both, because it means you can derive either one from the other, and you can see right away why Dijkstra's algorithm 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 neighbors in. That is the entire skeleton, and it does not care what the container is. A STACK gives you depth-first: the most recently found node comes out next, so you dive down one branch to the end before backing up. A QUEUE gives you breadth-first: the earliest found node comes out next, so you finish everything one step away before looking at anything two steps away. A PRIORITY QUEUE gives you Dijkstra's algorithm, where the cheapest node so far 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 576 practice puzzles