breadth-first search

A graph search that visits the start vertex, then all its neighbours, then all of theirs, spreading out in waves using a FIFO queue.

In more detail

Because vertices come off the queue in order of distance, the first time BFS reaches a vertex is along a path with the fewest edges. It runs in O(V + E) time. Recording each vertex's parent lets you rebuild the shortest path afterwards.

Example

The course uses it with collections.deque to walk a dependency graph and record how deep it goes.

Related terms

Taught in

References