BFS Theory

Definition

Given a graph G = (V, E) and a source vertex s, BFS systematically explores the edges of G to discover every vertex reachable from s. It computes the shortest path distance (in number of edges) from s to every discovered vertex and records a breadth-first tree (parent pointers) that captures shortest paths.

Algorithm Steps

1. Initialize all vertices as undiscovered (WHITE) with infinite distance.
2. Mark source s as GRAY (discovered), distance 0, and enqueue it.
3. While queue not empty: dequeue front u.
4. For each neighbor v of u: if WHITE, mark GRAY, set parent, distance = dist[u] + 1, enqueue v.
5. After exploring all neighbors of u, mark u BLACK (fully processed).
6. Continue until queue empty. Parents form shortest path tree.

Time & Space Complexity

Each vertex enqueued at most once; each edge considered at most twice (undirected) or once (directed).

Pseudocode

1BFS(G, s):
2  for each vertex v in G:
3    color[v] ← WHITE
4    dist[v] ← ∞
5    parent[v] ← NIL
6  color[s] ← GRAY
7  dist[s] ← 0
8  enqueue(Q, s)
9  while Q not empty:
10    u ← dequeue(Q)
11    for each neighbor v of u:
12      if color[v] = WHITE:
13        color[v] ← GRAY
14        dist[v] ← dist[u] + 1
15        parent[v] ← u
16        enqueue(Q, v)
17    color[u] ← BLACK

Applications

• Shortest path in unweighted graphs
• Level-order traversal of trees
• Finding connected components (with repeated BFS/DFS)
• Checking bipartiteness
• Peer-to-peer network distance / social graphs
• Web crawlers exploring outward from a seed

Advantages & Disadvantages

Example Problems

• Minimum number of moves in a board game (unweighted state graph)
• Shortest path in a maze/grid (4-direction or 8-direction)
• Friend-of-friend distance in social network
• Detect if graph is bipartite
• Compute distances from multiple sources (multi-source BFS)