Running time for Breadth-First-Search vs Depth-First-Search Can someone explain why BFS is $O(V + E)$ whereas DFS is $\Theta(V + E)$.
I understand the definitions of both notations, but I just don't see why the bound for DFS should be tighter than that of BFS.

Is it because DFS is guarenteed to visit all vertices and hence has the lower bound $\Omega(V+E)$?

Note: I am studying the CLRS book, which is where the running times is coming from
The running time of both BFS and DFS are $\Theta(V+E)$ since both of them are guaranteed to visit every vertex and every edge at least once. Note that we are talking about the situation when the input graph is a connected graph whose edges are given by adjacency-list, the most common situation (in the course of your study).

It is not surprising that the CLRS book presents the running time of BFS as $O(V+E)$ even though $\Theta(V+E)$ is the optimal asymptotic bound for its running time. It is actually a general practice that the running time of an algorithm is described in term of big $O$ even though it might be possible to describe in term of big $\Theta$. The reason is that how tight we can bound the  running time of an algorithm from above is the major concern for many situations.