Problem Solving with Algorithms and Data Structures using Java The Interactive Edition

The general running time for depth-first search is as follows. The loops in dfs both run in $O(|V|)\text{,}$ not counting what happens in dfs_visit, since they are executed once for each vertex in the graph. In dfs_visit the loop is executed once for each edge in the adjacency list of the current vertex. Since dfs_visit is only called recursively if the vertex is white, the loop will execute a maximum of once for every edge in the graph, or $O(|E|)\text{.}$ Therefore, the total time for depth-first search is $O(|V|+|E|)\text{.}$