Breadth-First Search — Animated Level-by-Level Traversal

The queue is key

BFS uses a FIFO queue. Dequeue, visit, enqueue unvisited neighbors. Levels emerge naturally.

The queue is key

BFS uses a FIFO queue. Dequeue, visit, enqueue unvisited neighbors. Levels emerge naturally.

Java template

Queue q = new LinkedList<>();
Set visited = new HashSet<>();
q.offer(start);
visited.add(start);
while (!q.isEmpty()) {
  Node cur = q.poll();
  process(cur);
  for (Node next : cur.neighbors)
    if (visited.add(next)) q.offer(next);
}

Shortest path (unweighted)

Distance to any node = level number. BFS gives shortest path in edges (not weights).

Multi-source BFS

Start with multiple sources in the queue. Every reachable node's distance = min over sources.