31251 Lec 9.4: Breadth-first search

In this video we go over breadth-first search. We motivate breadth-first search by talking about the single-source shortest paths problem. We see that depth-first search does not solve this problem, but that breadth-first search can. We go through a detailed example of the execution of breadth-first search on a graph. Finally we analyse its running time and show that it generates a shortest path tree.

Links to code: