Graphs5 min read

Breadth-First Search

Explore a city map ring by ring — nearest neighbors first

time: \(O(V+E)\)space: \(O(V)\)

You're standing in city A with a map of roads. You want to find the shortest route to every other city. The strategy: first visit every city directly connected to A. Then visit every city connected to those cities. Then the next ring out. And so on.

This ring-by-ring expansion is Breadth-First Search (BFS). It explores all cities at distance 1 before any city at distance 2, all cities at distance 2 before distance 3, and so forth.

The Queue is the key

BFS needs a queue — a first-in, first-out waiting room. Cities waiting to be explored line up in order. The city at the front of the line gets explored next, and its unvisited neighbors join the back of the line.

pseudocode

function bfs(graph, start):
  queue = [start]
  visited = {start}

  while queue is not empty:
    city = queue.shift()          // dequeue front
    process(city)

    for neighbor of graph[city]:
      if neighbor not in visited:
        visited.add(neighbor)
        queue.push(neighbor)      // enqueue back

Why BFS finds the shortest path

BFS visits cities in order of their distance from the start. The first time BFS reaches a city, it has taken the shortest possible route to get there — because it always finishes exploring shorter paths before longer ones.

This property only holds for unweighted graphs. If roads have different lengths (weights), use Dijkstra's algorithm instead.

Level-order traversal

BFS naturally produces a level-order traversal. Level 0 is just the start node. Level 1 is all direct neighbors. Level 2 is all neighbors of neighbors. You can track the level by noting when the current layer of the queue is exhausted before starting the next.

◈ Watch BFS explore

← → arrow keys to step · click elements to interact

BFS Traversal

from collections import deque

graph = {
    'A': ['B','C'],
    'B': ['A','D','E'],
    'C': ['A','F'],
    'D': ['B'], 'E': ['B'], 'F': ['C']
}

def bfs(start):
    visited = {start}
    q = deque([start])
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                q.append(nb)
    return order

print(bfs('A'))  # ['A','B','C','D','E','F']

Output

['A', 'B', 'C', 'D', 'E', 'F']

Note: BFS guarantees the shortest path in an unweighted graph. The queue enforces level-by-level order — no city is visited at distance d+1 until all distance-d cities are done.

Complexity

TimeEvery city and road visited once

Linear\(O(V+E)\)

SpaceQueue and visited set hold up to V cities

Linear\(O(V)\)

Shortest Path (Hop Count)

from collections import deque

graph = {'A':['B','C'],'B':['A','D','E'],'C':['A','F'],'D':['B'],'E':['B'],'F':['C']}

def shortest_path(start, end):
    dist = {start: 0}
    q = deque([start])
    while q:
        node = q.popleft()
        for nb in graph[node]:
            if nb not in dist:
                dist[nb] = dist[node] + 1
                if nb == end: return dist[nb]
                q.append(nb)
    return -1

print(shortest_path('A', 'F'))  # 2  (A→C→F)
print(shortest_path('A', 'D'))  # 2  (A→B→D)

Output

2
2

Challenge

Quick check

Why does BFS use a queue rather than a stack?

Depth-First Search

Follow one road as far as it goes before backtracking

→

Graph Representation

How to store a map of cities and roads in memory

→

Dijkstra's Algorithm

GPS for graphs — find the cheapest route from one node to all others

→