Breadth-First Search

Explore nodes level by level using a queue, guaranteeing the shortest path in unweighted graphs and trees.

Explore nodes level by level using a queue, guaranteeing the shortest path in unweighted graphs and trees.

All nodes at distance d from the source are fully processed before any node at distance d+1 is dequeued.

A FIFO queue processes nodes in non-decreasing distance order from the source — it visits the shortest path first by construction.

Marking nodes visited on enqueue (not dequeue) prevents duplicate enqueuing and keeps time O(V + E).