Traverse the unweighted directed graph with edges 0 → 1, 0 → 2, 1 → 3, 2 → 3 starting from vertex 0. An adjacency list stores 0: [1, 2], 1: [3], 2: [3], 3: []. Breadth-first search will visit in increasing edge count using a queue.
1. Build the neighbor representation
Four vertices and four edges fit a list in O(V + E) space. Scanning all neighbors of 0 costs proportional to its degree, 2. A matrix would store 16 cells for the same facts, wasteful here.
2. Initialize the frontier
Enqueue 0 with distance 0 and mark it visited at enqueue time, so no second edge can add it again. Queue: [0]. Distances: {0: 0}.
3. Expand one vertex
Dequeue 0, scan neighbors 1 and 2: both unvisited, so mark, set distance 1, enqueue. Queue: [1, 2]. Dequeue 1, scan neighbor 3: unvisited, so mark, set distance 2, enqueue. Queue: [2, 3]. Dequeue 2, scan neighbor 3: already visited, skip. Queue: [3]. Dequeue 3: no neighbors.
4. Mark each discovery once
Marking at enqueue, not dequeue, keeps each vertex queued exactly once even though two edges reach 3. Marking late would have enqueued 3 twice and doubled its work. The queue order 0, 1, 2, 3 is the nondecreasing-distance order BFS promises.
5. Return reachability or distance
Distances {0: 0, 1: 1, 2: 1, 3: 2} are fewest-edge distances, found in O(V + E). They are not minimum costs if edges carried weights; Dijkstra's algorithm handles non-negative weights, and negative edges need Bellman-Ford. One launch from 0 reached everything here, but a graph with an unreachable component needs a fresh launch per unvisited vertex. For the full guide, continue with Graph Algorithms.
Hardware, runtime, and observability notes
When tracing Trace Breadth-First Search Across Four Vertices in a live production environment (subsystem: execution, primary layer: runtime), keep the following step-level cost model and diagnostic checklist in mind:
- Step 1 (runtime): Build the neighbor representation — verifies state invariants before advancing the execution pointer.
- Step 2 (runtime): Initialize the frontier — verifies state invariants before advancing the execution pointer.
- Step 3 (runtime): Expand one vertex — verifies state invariants before advancing the execution pointer.
- Step 4 (runtime): Mark each discovery once — verifies state invariants before advancing the execution pointer.
- Step 5 (runtime): Return reachability or distance — verifies state invariants before advancing the execution pointer.
Every transition across the runtime boundary carries both a direct CPU/memory cost (cache-line fills, descriptor lookups, lock acquisitions, or context switches) and a tail-latency queueing risk under contention. To verify this trace on your own service, capture latency histograms and hardware/kernel counters across each step boundary, compare cold-cache versus warm-cache execution paths, and confirm that error or timeout branches release all acquired descriptors, locks, and buffers cleanly.