CODEWITHSUNDEEP
time-complexitygraph-algorithmanalysisbreadth-first-searchadjacency-list
Siddharth Thevaril
Siddharth Thevaril

Reputation: 3788

BFS (Breadth First Search) Time complexity at every step

BFS(G,s)

1   for each vertex u ∈ G.V-{s}
2       u.color = WHITE
3       u.d = ∞
4       u.π = NIL
5   s.color = GRAY
6   s.d = 0
7   s.π = NIL
8   Q ≠ Ø
9   ENQUEUE(Q, s)
10  while Q ≠ Ø
11      u = DEQUEUE(Q)
12      for each v ∈ G.Adj[u]
13          if v.color == WHITE
14              v.color = GRAY
15              v.d = u.d + 1
16              v.π = u
17              ENQUEUE(Q, v)
18      u.color = BLACK

The above Breadth First Search code is represented using adjacency lists.

Notations -

  • G : Graph
  • s : source vertex
  • u.color : stores the color of each vertex u ∈ V
  • u.π : stores predecessor of u
  • u.d = stores distance from the source s to vertex u computed by the algorithm

    Understanding of the code (help me if I'm wrong) -

     1. As far as I could understand, the ENQUEUE(Q, s) and DEQUEUE(Q) operations take O(1) time.<br>

 2. Since the enqueuing operation occurs for exactly one time for one vertex, it takes a total O(V) time. 

 3. Since the sum of lengths of all adjacency lists is |E|, total time spent on scanning adjacency lists is O(E).

 4. Why is the running time of BFS is O(V+E)?.


    Please do not refer me to some website, I've gone through many articles to understand but I'm finding it difficult to understand.
    Can anyone please reply to this code by writing the time complexity of each of the 18 lines?

    Upvotes: 0

    Views: 435

    • Answers (1)

    Ranald Lam
    Ranald Lam

    Reputation: 496

    Lines 1-4: O(V) in total

    Lines 5-9: O(1) or O(constant)

    Line 11: O(V) for all operations of line 11 within the loop (each vertice can only be dequeued once)

    Lines 12-13: O(E) in total as you will check through every possible edge once. O(2E) if the edges are bi-directional.

    Lines 14-17: O(V) in total as out of the E edges you check, only V vertices will be white.

    Line 18: O(V) in total

    Summing the complexities gives you O(4V + E + 1) which simplifies to O(V+E)

    New: It is not O(VE) because at each iteration of the loop starting at line 10, lines 12-13 will only loop through the edges the current node is linked to, not all the edges in the entire graph. Thus, looking from the point of view of the edges, they will only be looped at most twice in a bi-directional graph, once by each node it connects with.

    Upvotes: 2

    Related Questions