5. Complexity
Roadmap (what we analyze in this part):
- Time complexity with adjacency lists
- Why each vertex is processed once
- Why each edge is examined at most twice
- Comparison with adjacency matrix
- Space complexity
- Structural insight
Now that correctness has been established, we analyze the algorithm from a computational perspective.
5.1 Time Complexity (Adjacency List)
O(|V| + |E|)
This bound is optimal for graph traversal.
5.2 Vertex Processing
- Discovered once
- Enqueued once
- Dequeued once
- Colored BLACK once
O(|V|)
5.3 Edge Examination
Each edge is examined at most twice (undirected case).
O(|E|)
5.4 Adjacency Matrix Case
O(|V|^2)
For sparse graphs, adjacency lists are asymptotically superior.
5.5 Space Complexity
O(|V|)
5.6 Structural Insight
- No revisits
- No redundant exploration
- Strict layer order enforced by FIFO
Next: Part 6 — BFS Tree & Path Reconstruction
With correctness and complexity understood, we now focus on what BFS actually produces: the predecessor pointers form a BFS tree, and that tree lets us reconstruct shortest paths from the source to any reachable vertex.