Breadth-First Search

graph

Click Generate New or press Play

Step 1 / 1

Ready

Speed

Explores all vertices at the present depth before moving to vertices at the next depth level.

Time Complexity

Best

\mathrm{O}\left(V + E\right)

Avg

\mathrm{O}\left(V + E\right)

Worst

\mathrm{O}\left(V + E\right)

Space Complexity

Aux

\mathrm{O}\left(V\right)

Queue + visited set — up to V nodes stored

Pseudocode

1procedure BFS(graph, start, end)

2queue.enqueue(start)

3while queue is not empty do

4node = queue.dequeue()

5for each neighbor of node do

6if not visited then queue.enqueue(neighbor)