TraversalO(V + E)· Level 01

Breadth-First Search (BFS)

Layer-by-layer traversal — shortest path in unweighted graphs.

Intuition

Imagine dropping a stone in a pond — the ripples expand outward in concentric circles. BFS visits all neighbors at distance 1, then distance 2, and so on. This guarantees the first time you reach any node, you've used the fewest possible edges.

Step-by-step

1
Pick a start vertex `s` and place it in a FIFO queue.
2
Mark `s` as visited.
3
While the queue is not empty: pop the front vertex `u`.
4
For every neighbor `v` of `u` that isn't visited: mark visited, record `parent[v] = u`, and enqueue `v`.
5
When the queue empties, every reachable vertex has been visited — `parent` holds the shortest-path tree.

Pseudocode

pseudocode

BFS(G, s):
  for each v in V: visited[v] = false
  Q = empty queue
  visited[s] = true
  Q.enqueue(s)
  while Q not empty:
    u = Q.dequeue()
    for v in G.neighbors(u):
      if not visited[v]:
        visited[v] = true
        parent[v] = u
        Q.enqueue(v)

Implementation (Python)

python

from collections import deque

def bfs(graph, start):
    visited = {start}
    parent = {start: None}
    queue = deque([start])

    while queue:
        u = queue.popleft()
        for v, _ in graph.neighbors(u):
            if v not in visited:
                visited.add(v)
                parent[v] = u
                queue.append(v)

    return parent

Real-world applications

Shortest path in unweighted graphs
Web crawlers
Peer-to-peer network broadcasting
Solving puzzles like Rubik's cube (state graph)