GO Classes DPP | GATE CS, DA | Algorithms | BFS Maximum Space

Answer 1

BFS stores vertices that have been discovered but have not yet been processed in a queue.

Therefore, the maximum space used by BFS depends on the maximum width of the tree.

Consider a complete binary tree.

At level $0: 1$ vertex

At level $1: 2$ vertices

At level $2: 4$ vertices

At level $k: 2^k$ vertices

For a complete binary tree containing $n$ vertices, the final full level contains a constant fraction of all vertices.

Thus, at some point the BFS queue can contain $\Theta(n)$ vertices simultaneously. 

Now consider a skewed tree or a path.

There is only a constant number of vertices at each level, so the BFS queue contains only $O(1)$ vertices at a time.

$\therefore$ Answer: B

Comments

Note: for a tree we don't need the visited array. Otherwise the space complexity in general graph will be O(V). Lol.