Breadth-first search

bfs(G, s)
  for each v ∈ V(G)                 [n]
    visited[v] ← false              [n]
    parent[v] ← v                   [n]
  queue ← { s }                     [1]
  visited[s] ← true                 [1]
  while queue not empty             [m]
    v ← dequeue                     [m]
    for each (v → u) ∈ E(G)         [m] - (a)
      if visited[u] = false         [m]
        enqueue u                   [m]
        visited[u] ← true           [m]
        parent[u] ← v               [m]

This algorithm is very similar to DFS. We replace the stack with a queue so that vertices are traversed in breadth-first order. Also, we can set parent[v] to u as soon as we discover v through an edge u → v because this edge must be part of a shortest path to v from s and therefore also part of a BFS tree. This is not true for DFS.

BFS takes \(O(n+m)\) time.

The number of times each statement is executed is shown on the right-hand side. The argument is similar to that of DFS. The number of enqueue and dequeue operations is at most \(m\) because the loop in step (a) is run at most once for a `v`.

Let G be any vertex reachable from s in G and the shortest path be \(k\) steps. Then, the sequence v, parent[v], parent[parent[v]], ... leads to s in at most \(k\) steps and represents a shortest path from s to v in G.

Use induction on \(k\).