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
Graph01234L0L1L2L1L2BFS from 0Queue: [0] Visit 0, enqueue 1, 2Queue: [1, 2] Visit 1, enqueue 3, 4Queue: [2, 3, 4] Visit 2 (no new)Queue: [3, 4] → Visit 3Queue: [4] → Visit 4Visit order:0 → 1 → 2 → 3 → 4

Notice the level-by-level structure: → →

Implementation#

  • Time Complexity: O(V + E), since it visits every vertex and edge once
  • Space Complexity: O(V), because the queue can hold up to O(V) nodes at once

Interactive Lab#

Let's take the example in this visualization: six vertices A to F joined by nine edges, with A marked as the source and E as the target. Press play and follow the queue. A is dequeued first and enqueues its neighbours B and D; B is dequeued next and adds C and E behind them. Every vertex one hop from A is coloured before any vertex two hops away. That is the entire guarantee BFS gives you, and it is why the path it reconstructs, A → B → E, is the shortest one by edge count.

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.

Python

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#

PropertyDFSBFS
Data structureStack / recursionQueue
Memory (dense graphs)LessMore
Finds shortest path✗✓ (unweighted)
Good forTopology, cycles, backtrackingShortest path, levels

What to Remember#

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.