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 in memory and also keep track of which vertices have been seen along with the current frontier. The frontier can, in the worst case, contain every vertex, and you store a visited marker for each vertex. At the same time, the graph itself, stored in memory (for example as an adjacency list), uses space proportional to V plus the number of edges E. When you account for both the graph storage and the auxiliary data (frontier and visited markers), the total space grows as O(V + E). That’s why the worst-case space complexity is O(V + E).

BFS needs to hold the graph in memory and also keep track of which vertices have been seen along with the current frontier. The frontier can, in the worst case, contain every vertex, and you store a visited marker for each vertex. At the same time, the graph itself, stored in memory (for example as an adjacency list), uses space proportional to V plus the number of edges E. When you account for both the graph storage and the auxiliary data (frontier and visited markers), the total space grows as O(V + E). That’s why the worst-case space complexity is O(V + E).