Why is $O(|V| + |E|)$ the bound on DFS and BFS instead of just $O(|E|)$?

In one sense I understand why the bound on BFS and DFS is $O(|V| + |E|)$. Every vertex gets considered, hence the $O(|V|)$, and over the course of considering all adjacent vertices, we end up considering $2|E| = O(|E|)$ vertices total because $\sum_{v \in V} d_v = 2|E|$. What I don't understand is why we even bother specifying $O(|V| + |E|)$ in the first place because it seems to me that the tightest bound you can really have in any situation is $O(|E|)$. I.e., it seems to me that the $O(|V|)$ doesn't help you at all. To see why, consider two cases:

• The graph is connected. Then of course $|E| \ge |V - 1|$.

• The graph isn't connected. Then you are "stuck" in the connected component you start in. Once again, inside the connected component $A$ you start in you have $|E_A| \ge |V_A - 1|$. Maybe there are more edges and vertices elsewhere. But once again the $O(|V|)$ seems redundant.

Another way I think about it: Adding a vertex alone doesn't create any more work since the vertex will just be floating in space. Adding edges can create extra work.

So why/when is the $O(|V|)$ useful?

You have missed an important element of graph search: the outer loop.

Here is typical pseudocode for a graph search algorithm:

S <- new empty set
T <- new empty set
for each vertex u in V:
    add u to T
    while T is not empty:
        v <- 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.

StackExchange Computer Science Q#120087, answer score: 3