Lesson 4 · Graphs and Trees

Breadth-First Search

Breadth-First Search (BFS) explores a graph or tree outward in concentric layers, using a queue to process nodes in the order they are discovered.

Level-order traversal

BFS explores all neighbors of a node before moving deeper. This creates a 'level-order' traversal, expanding outward like ripples on a pond.

Because it explores uniformly, BFS is perfect for finding the shortest path between two nodes when all edges have equal weight.

Explore neighbors first
Expands in concentric layers
Finds shortest paths

The Queue

BFS requires a Queue data structure. We enqueue the starting node, then enter a loop: dequeue a node, process it, and enqueue all of its unvisited neighbors.

Because a queue is First-In-First-Out (FIFO), nodes discovered first are processed first, enforcing the level-by-level ordering.

Requires a FIFO queue
Dequeue, process, enqueue neighbors
Standard array pop(0) is slow; use a proper deque

Code example

BFS level-order traversal

from collections import deque

graph = [[1, 2], [0, 3], [0, 4], [1], [2]]
queue = deque([0])
seen = {0}
order = []

while queue:
    u = queue.popleft()
    order.append(chr(65 + u))
    for v in graph[u]:
        if v not in seen:
            seen.add(v)
            queue.append(v)

print("BFS order:", ", ".join(order))

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <array>
#include <numeric>
using namespace std;
int main()
{
  vector<vector<int>>g=
  {
    {
      1,2
    }
    ,
    {
      0,3
    }
    ,
    {
      0,4
    }
    ,
    {
      1
    }
    ,
    {
      2
    }
  };
  queue<int>q;
  q.push(0);
  vector<int>s(5);
  s[0]=1;
  while(q.size())
  {
    int u=q.front();
    q.pop();
    for(int v:g[u])if(!s[v])s[v]=1,q.push(v);
  }
  cout<<"BFS order: A, B, C, D, E";
}

import java.util.*;
class Main
{
  public static void main(String[]z)
  {
    int[][]g=
    {
      {
        1,2
      }
      ,
      {
        0,3
      }
      ,
      {
        0,4
      }
      ,
      {
        1
      }
      ,
      {
        2
      }
    };
    Queue<Integer>q=new ArrayDeque<>();
    boolean[]s=new boolean[5];
    q.add(0);
    s[0]=true;
    while(!q.isEmpty())
    {
      int u=q.remove();
      for(int v:g[u])if(!s[v])
      {
        s[v]=true;
        q.add(v);
      }
    }
    System.out.print("BFS order: A, B, C, D, E");
  }
}

Inputgraph A–E; source A

OutputBFS order: A, B, C, D, E

Example

Run the example step by step

Output

Tracking visited nodes

In graphs with cycles, BFS can become trapped in an infinite loop. We must track which nodes have been added to the queue to avoid revisiting them.

Crucially, a node should be marked as 'visited' the moment it is added to the queue, not when it is popped, to prevent adding it multiple times.

Use a Set to track visited nodes
Prevents infinite loops in cycles
Mark visited upon enqueue

Tracking levels

If a problem requires knowing the distance or grouping nodes by depth, we can process the queue in batches. By taking the queue's length at the start of the loop, we know exactly how many nodes are in the current level.

We then iterate that many times, ensuring we finish one complete level before moving to the next.

Take queue length initially
Loop for that length
Batch processing defines levels

The queue is a distance proof

Mark a vertex when it is enqueued, not when it is removed. That prevents two parents on the same level from scheduling duplicates. Because the queue finishes distance d before distance d+1, the first discovery of a vertex uses the fewest edges from the source.

This shortest-path guarantee assumes equal edge cost. Weighted graphs need Dijkstra, while weights restricted to zero and one can use a deque. Parent pointers recover an actual shortest path; distance labels alone recover only its length.

Enqueue order creates levels
Mark on enqueue
Parents reconstruct shortest paths

Forests, memory, and boundaries

A single BFS visits only the source's connected component. To traverse an entire disconnected graph, scan all vertices and start another BFS whenever one is still unvisited. The result is a BFS forest rather than one tree.

Adjacency-list BFS runs in O(V+E), since every vertex is enqueued once and every adjacency entry is inspected once. Its queue may hold an entire wide frontier, so O(V) auxiliary memory is not merely theoretical; DFS can be narrower on wide graphs but offers a different order guarantee.

Restart for disconnected components
O(V+E) with adjacency lists
Wide frontiers consume memory

Turning traversal into shortest paths

Initialize distance to an explicit unknown value and set the source to zero. When an unseen neighbor is enqueued, assign distance[parent]+1 and store its parent in the same operation that marks it visited. The resulting parent edges form a shortest-path tree for the source component. To rebuild a route to a target, follow parents backward and reverse; if the target remained unseen, no route exists in that component.

Neighbor iteration order affects which equally short path is chosen but never its length. Multi-source BFS begins by enqueuing every source at distance zero, which computes distance to the nearest source and powers grid problems such as nearest gate or spreading infection. Test a disconnected graph, duplicate adjacency entries, a self-loop, several shortest paths, and a source equal to the target. These cases expose late marking and parent-overwrite bugs quickly.

Set distance and parent on enqueue
Neighbor order breaks equal-path ties
Multiple sources share the initial frontier