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

0

9 Answers

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

5

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 Σv 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 Σv deg(v) = 2m
2

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.

3

An intuitive explanation to this is by simply analysing a single loop:

  1. visit a vertex -> O(1)
  2. 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 => O(1) + O(e) => O(V) + O(E)

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.

3

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

3

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)

In Bfs, each neighboring vertex is inserted once into a queue. This is done by looking at the edges of the vertex. Each visited vertex is marked so it cannot be visited again: each vertex is visited exactly once, and all edges of each vertex are checked. So the complexity of BFS is V+E. In DFS, each node maintains a list of all its adjacent edges, then, for each node, you need to discover all its neighbors by traversing its adjacency list just once in linear time. For a directed graph, the sum of the sizes of the adjacency lists of all the nodes is E(total number of edges). So, the complexity of DFS is O(V + E).

It's O(V+E) because each visit to v of V must visit each e of E where |e| <= V-1. Since there are V visits to v of V then that is O(V). Now you have to add V * |e| = E => O(E). So total time complexity is O(V + E).