Breadth-First Search
Explore layer by layer with a queue. Discovers shortest paths in unweighted graphs.
BFS and DFS: Breadth-first from 0
Visited in order 0, 1, 2, 3, 5, 4. The number on each vertex is its distance from 0, and the highlighted edges are the shortest paths back to it. Every vertex was reached. Each vertex was enqueued once and each edge looked at twice: O(V + E).
Cost
- Best
- O(V + E)
- Average
- O(V + E)
- Worst
- O(V + E)
- Space
- O(V)
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
BFS and DFS covers these too, in the same run.