Why 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 think the time complexity will be:

 v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges) 

where v is vertex 1 to n

First, is that what I said correctly? Secondly, it’s like O(N + E) , and intuition as to why it would be really nice. Thanks

Answer 1

Your amount

 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) , and the other is O(E) .

Answer 2

DFS (analysis):

• Setting / getting the vertex / edge label takes O(1) time
• Each vertex is marked twice
  • once as UNEXPLORED
  • once visited
• Each rib is marked twice
  • once as UNEXPLORED
  • once as DISCOVERY or BACK
• The randomEdges method is called once for each vertex.
• DFS works in O(n + m) time if the graph is represented by an adjacency list structure
• Recall that Σv deg(v) = 2m

BFS (analysis):

• Setting / getting the vertex / edge label takes O (1) time
• Each vertex is marked twice
  • once as UNEXPLORED
  • once visited
• Each rib is marked twice
  • once as UNEXPLORED
  • once as DISCOVERY or CROSS
• Each vertex is inserted once in the sequence Li
• The randomEdges method is called once for each vertex.
• BFS works in O(n + m) time if the graph is represented by an adjacency list structure
• Recall that Σv deg(v) = 2m

Answer 3

It is very simplified without much formality: each edge is considered exactly twice, and each node is processed exactly once, so the complexity should be constant multiple of the number of edges, as well as the number of vertices.

Answer 4

The 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).

Therefore, O (2E + V) is written as O (E + V)

since the difference between n ^ 2 and n matters, but not between n and 2n.

Answer 5

I think that each edge was examined twice, and each node was visited once, so the total time complexity should be O (2E + V).

Answer 6

A brief but simple explanation:

In the worst case, you will need to visit the entire top and edge, therefore the temporal complexity in the worst case is O (V + E)

Answer 7

An intuitive explanation for this is a simple analysis of one cycle:

• visit the top → O (1)
• the for loop on all falling edges → O (e), where e is the number of edges falling on a given vertex v.

Thus, the total time for one cycle is O (1) + O (e). Now summarize it for each vertex when each vertex is visited once. This gives

Sigma_i

 p { height: 50px; line-height: 50px; } span { position: relative; font-size: 2.5em; display: inline-block; line-height: .7em; vertical-align: middle; } span:before { font-size: 12px; display: block; position absolute; left: 0; top: 0; content: "V"; width: 22px; text-align: center; } span:after { font-size: 12px; display: block; position absolute; left: 0; bottom: 0; content: "k = 1"; width: 27px; text-align: center; } 

 <p> <span>&Sigma;</span> O(1) + O(e) => <span>&Sigma;</span> O(1) + <span>&Sigma;</span> O(e) => O(V) + O(E) </p> 

[O (1) + O (e)]