What is the worst-case space complexity of breadth-first search on a graph in terms of vertices V and edges E?

What is the worst-case space complexity of breadth-first search on a graph in terms of vertices V and edges E?

• A. O(V + E)
• B. O(V)
• C. O(E)
• D. O(1)

Answer: (A)

BFS needs to hold the graph structure plus the data it uses to track progress. It processes vertices level by level using a queue and a visited set, which consume space that scales with the number of vertices. At the same time, the graph itself—whether stored as adjacency lists or a matrix—uses space proportional to both vertices and edges, specifically O(V + E). In the worst case, you’re keeping both the graph representation and the BFS data structures in memory, so the total space requirement is O(V + E). That’s why this option is the best choice.

Using only O(V) would miss the edge component, since the graph’s edges contribute to memory usage. O(E) would miss the vertices. O(1) isn’t possible because you must store at least the frontier and the visited markers.