AlgoScope

Breadth-First Search

Explore layer by layer with a queue. Discovers shortest paths in unweighted graphs.

Graph traversal, algorithm, beginnerAlso called BFS
Breadth-first search visited 0, 1, 2, 3, 5, 4.001121324352
Breadth-first search visited 0, 1, 2, 3, 5, 4.001121324352

BFS and DFS: Breadth-first from 0

Result, step 8 of 8

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)

Leads to

Topics that need this one first.

Taught by the same lesson

BFS and DFS covers these too, in the same run.