Breadth First Search

Breadth First Search

Breadth first search, or BFS, explores a graph outward in rings. It visits all nodes one step away, then all nodes two steps away, and so on. This level order makes it the natural tool for shortest paths in an unweighted graph.

The queue

BFS uses a first in first out queue. Start by enqueuing the source node and marking it visited. Then repeatedly:

• Remove the node at the front of the queue.
• Look at its neighbors.
• Enqueue each unvisited neighbor and mark it visited immediately.

Marking on enqueue, not on dequeue, prevents adding the same node twice.

Why level order

Because nodes are processed in the order they were discovered, the first time you reach a target is along a path with the fewest edges. Storing each node's discoverer lets you reconstruct that path.

BFS visits every node and edge once, so its cost is proportional to the graph size.

Key idea

A queue drives level by level exploration, so BFS finds the fewest edge path in an unweighted graph.