data structures - Explanation of runtimes of BFS and DFS

Question

Why are the running times of BFS and DFS O(V+E), especially when there is a node that has a directed edge to a node that can be reached from the vertex, like in this example in the following site

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm

question from:https://stackoverflow.com/questions/6850357/explanation-of-runtimes-of-bfs-and-dfs

Answer 1

E is the set of all edges in the graph, as G={V,E}. So, |E| is count of all edges in the graph.

This alone should be enough to convince you that the overall complexity can't be |V| times |E|, since we are not iterating over all the edges in the graph for each vertex.

In the adjacency list representation, for each vertex v, we only traverse those nodes which are adjacent to it.

The |V| factor of the |V|+|E| seems to come from the number of queue operations done.

Note that the complexity of the algorithm depends on the data structure used. effectively we are visiting each piece of information present in the representation of the graph, which is why for matrix representation of the graph, complexity becomes V squared.

Quoting from Cormen,

"The operations of enqueuing and dequeuing take O(1) time, so the total time devoted to queue operations is O( V). Because the adjacency list of each vertex is scanned only when the vertex is dequeued, each adjacency list is scanned at most once. Since the sum of the lengths of all the adjacency lists is Θ(E), the total time spent in scanning adjacency lists is O( E). The overhead for initialization is O( V), and thus the total running time of BFS is O( V + E)."