Sign in to watch this lesson
Algorithms - Graphs I · 5:28
Breadth-First Search
Set the start cell of a maze on fire and watch the flames spread one step per second: that is breadth-first search, and the second the fire reaches a cell is its shortest distance. We build it from a queue whose front always holds the smallest distance, restore the route with a parent array, see why a cell must be marked when it is pushed (on a complete graph of 2,000 nodes, marking on pop pushes about two million entries), light many sources at once, and use two searches to find every edge on a shortest path.
You will learn
- Implement BFS with a queue, a distance array and a parent array, marking each vertex as used when it is pushed, in O(n + m)
- Explain why BFS gives shortest paths in unweighted graphs (the queue holds at most two consecutive distances) and why it fails with weights
- Restore a shortest path by walking the parent array back from the target and reversing it
- Use multi-source BFS for distances to the nearest source, and two BFS runs to decide which edges lie on some shortest a-b path