Why is $O(|V| + |E|)$ the bound on DFS and BFS instead of just $O(|E|)$?
You have missed an important element of graph search: the outer loop.

Here is typical pseudocode for a graph search algorithm:

S &lt;- new empty set
T &lt;- new empty set
for each vertex u in V:
    add u to T
    while T is not empty:
        v &lt;- remove some element from T
        add v to S
        do something with v
        for each vertex w that is adjacent to v:
            if w is not in S and not in T:
                add w to T


Notice the outer loop on the variable u. This loop is present in some descriptions of DFS/BFS/etc. and absent in others. Why is this? The answer is that graph searches are used for different purposes. Sometimes, you have a particular start vertex u and you just want to search for everything that is reachable from u. However, other times you are using the graph search to find the connected components of the graph, or as part of an algorithm for computing some other property of the entire graph such as biconnected components. In these cases, the outer loop is necessary.

The crucial special property of graph search is that, even with the outer loop, the runtime is still bounded by $O(|V| + |E|)$, and not just by $O(|V| \cdot |E|)$. This property is what makes efficient algorithms possible for computing connected components, etc.



It's also worth noting that the $O(|V| + |E|)$ bound assumes that the white/gray/black status of a vertex (i.e. which set it is in) can be checked and modified in $O(1)$ time. This can be achieved by creating an array of size $V$, or by attaching a flag to each vertex; either way, it takes $O(V)$ time to initialize all the vertices into the white set at the start of the algorithm. If you don't use one of these methods, you probably have to add a logarithmic overhead for tracking the vertices in set data structures. This is true even in cases where you don't need the outer loop.