BFS Algorithm — Detail & Time Complexity

Algorithm (Queue)

BFS(G, s):
  for each v in V: color[v]=WHITE, dist[v]=∞, parent[v]=NIL
  color[s]=GRAY; dist[s]=0; Q=queue(); ENQUEUE(Q,s)
  while Q ≠ ∅:
    u=DEQUEUE(Q)
    for each v in Adj[u]:
      if color[v]==WHITE:
        color[v]=GRAY; dist[v]=dist[u]+1; parent[v]=u; ENQUEUE(Q,v)
    color[u]=BLACK

Variants output traversal order by recording dequeue order.

Example

Graph A→B,C etc, start A: queue [A] → visit A enqueue B,C → queue [B,C] → dequeue B enqueue D → [C,D] → dequeue C enqueue E → [D,E] → etc. Order A,B,C,D,E.

Time Complexity

• With adjacency list: Each vertex enqueued/dequeued once $O(V)$, each adjacency list scanned once $O(E)$ → $O(V+E)$.
• With adjacency matrix: scan row of $V$ entries per vertex → $O(V^2)$.

Space $O(V)$ for queue + color/dist arrays.

Properties

• Computes single-source shortest path (in edges) for unweighted graphs: dist[v] = minimum number of edges s→v.
• Produces BFS tree (parent pointers).
• Used as subroutine in Edmonds-Karp max flow, bipartite testing (2-coloring by levels), connected components.
• BFS levels correspond to distance layers; can also detect cycles / test bipartiteness by parity.