Why is the Time Complexity of DFS Algorithm O(|V| + |E|) instead of O(|E|)?

Question

I'm trying to understand time complexity in the context of graph algorithms, especially Depth-First Search (DFS). As far as I understand, time complexity indicates how the execution time of an algorithm grows as the input size increases. For graph algorithms, particularly DFS, I believe execution time directly depends on the number of recursive calls, which is directly linked to the number of edges rather than vertices.

Consider an edge {u, v} in a graph. Two DFS calls occur: the first when visiting u's neighbors and the second when visiting v's neighbors. In this scenario, the number of recursive calls seems to depend solely on the number of edges.

Given this, why do we mention vertices (V) in time complexity analyses of graph algorithms? It seems that V is not directly utilized in the calculation of recursive calls in DFS. Could someone clarify the role of vertices in the time complexity of graph algorithms, especially when considering DFS? Thank you!

Answer 1

DFS also does some work for each vertex of the graph. Consider a graph with $n$ vertices and 0 edges. DFS doesn't terminate immediately; it takes $O(n)$ steps before it terminates.

In most graphs, the difference between $O(|V|+|E|)$ vs $O(|E|)$ is immaterial, as in most graphs, we have $|E| \ge |V|$. But in the special case of graphs where $|E| \ll |V|$, the difference matters. $O(|V|+|E|)$ is correct in both cases.