Why is the time complexity of both DFS and BFS O V E

Question

The basic algorithm for BFS   set start vertex to visited  load it into queue  while queue not empty     for each edge incident to vertex          if its not visited              load into queue              mark vertex   So I would think the time complexity would be     v1    incident edges    v2    incident edges           vn    incident edges     where v is vertex 1 to n  Firstly  is what I ve said correct   Secondly  how is this O N   E   and intuition as to why would be really nice   Thanks

User · Answer

Time complexity is O E V  instead of O 2E V  because if the time complexity is n 2 2n 7 then it is written as O n 2      Hence  O 2E V  is written as O E V    because difference between n 2 and n matters but not between n and 2n

User · Answer

DFS analysis     Setting getting a vertex edge label takes O 1  time Each vertex is labeled twice  once as UNEXPLORED once as VISITED  Each edge is labeled twice  once as UNEXPLORED once as DISCOVERY or BACK  Method incidentEdges is called once for each vertex DFS runs in O n   m  time provided the graph is represented by the adjacency list structure Recall that Sv deg v    2m   BFS analysis     Setting getting a vertex edge label takes O 1  time Each vertex is labeled twice  once as UNEXPLORED once as VISITED  Each edge is labeled twice  once as UNEXPLORED once as DISCOVERY or CROSS  Each vertex is inserted once into a sequence Li Method incidentEdges is called once for each vertex BFS runs in O n   m  time provided the graph is represented by the adjacency list structure Recall that Sv deg v    2m

User · Answer

Short but simple explanation      I the worst case you would need to visit all the vertex and edge hence   the time complexity in the worst case is O V E

User · Answer

Very simplified without much formality  every edge is considered exactly twice  and every node is processed exactly once  so the complexity has to be a constant multiple of the number of edges as well as the number of vertices

User · Answer

I think every edge has been considered twice and every node has been visited once  so the total time complexity should be O 2E V

User · Answer

An intuitive explanation to this is by simply analysing a single loop    visit a vertex -  O 1  a for loop on all the incident edges -  O e  where e is a number of edges incident on a given vertex v    So the total time for a single loop is O 1  O e   Now sum it for each vertex as each vertex is visited once  This gives   For every V   gt        O 1             O e     gt  O V    O E

User · Answer

Your sum  v1    incident edges    v2    incident edges           vn    incident edges    can be rewritten as   v1   v2         vn      incident edges v1     incident edges v2           incident edges vn     and the first group is O N  while the other is O E

User · Answer

It s O V E  because each visit to v of V must visit each e of E where  e   lt   V-1  Since there are V visits to v of V then that is O V   Now you have to add V    e    E   gt  O E   So total time complexity is O V   E

[algorithm] Why is the time complexity of both DFS and BFS O( V + E )

Examples related to algorithm

Examples related to time-complexity

Examples related to graph-theory

Examples related to breadth-first-search