Breadth-First Search — Level-by-Level Traversal

What Is BFS?

Breadth-First Search (BFS) explores a graph level by level. It visits all neighbours of the starting node first, then all neighbours of those neighbours, and so on — expanding outward like ripples in a pond.

The key data structure is a queue (FIFO). DFS uses a stack (or recursion); BFS uses a queue.

How It Works

1. Add the start node to the queue and mark it visited
2. While the queue is not empty:
   • Dequeue a node
   • Process it
   • Enqueue all its unvisited neighbours, marking them visited

Notice the level-by-level structure: → →

Implementation

• Time Complexity: O(V + E) — visits every vertex and edge once
• Space Complexity: O(V) — queue holds at most one full level

Interactive Lab

BFS Finds the Shortest Path

In an unweighted graph, BFS guarantees the shortest path (fewest edges) from the start to every reachable node. The first time BFS reaches a node is always via the shortest route.

Key Applications

• Shortest path in unweighted graphs (social networks, maps)
• Web crawlers — explore pages level by level
• Network broadcasting — how packets propagate
• Level-order traversal of binary trees
• Multi-source BFS — flood fill (paint bucket tool), spreading fire

DFS vs BFS Summary

Key Takeaway

BFS is the right tool whenever you care about distance from the source. For shortest-path problems on unweighted graphs, BFS is optimal. The queue ensures nodes are processed in order of their distance from the start.