Breadth First Search Analysis

The analysis of the non-recursive version of Depth First Search is identical to Breadth First Search. We first consider a rough analysis of the algorithm in order to develop some intuition. We then build on this analysis to provide a more accurate estimate.

Here is the pseudocode for the algorithm along with the estimated time complexity for each line:

The time complexity estimates in the pseudocode above come from the following observations:

• The first point to consider is the complexity of the operations of the Queue data structure.
• The other important point is that the body of the while loop, will be executed V times – the number of vertices in the graph. This may not be clear immediately, but it follows from the
  fact that each vertex will enter the Queue exactly once and will leave the Queue exactly once. This is ensured by the coloring strategy – once a vertex enters the Queue it is colored GRAY
  which prevents it from entering the Queue twice. This mean that Line 7, P op(Q), which is executed every time through the while loop is executed at most V times (once per vertex) after which the Queue is empty.
• The final point to note is that the for loop in Line 9 will execute at most E times. After all, the for loop simply looks at the adjacent edges of v and at most we may have to examine all edges in the graph.

For overall the time complexity, individually we have

1. Init(Lines 1 : 2) takes O(V ) time
2. Setup(Lines 3 : 5) takes O(1) time
3. Search(Lines 6 : 12) can be divided into
4. Finish(Lines 7 : 8) + Explore(Lines 9 : 12)
   That is for each vertex v we perform a finish step (pop and mark), which takes O(1) time and we explore its neighbors, which takes at most O(E) times, i.e. at most all edges need to be
   explored. Thus per vertex we spend O(E) time for Finish and Explore, so for all vertices Search(Lines 6 : 12) takes O(V ∗ E)

Finally, the BFS time complexity is
Init(Lines 1 : 2) + Setup(Lines 3 : 5) + Search(Lines 6 : 12) = O(V ) + O(1) + O(V ∗ E) =  O(V ∗ E) since this is the dominating term.

If the graph is fully connected (dense graph), i.e. every vertex is connected to every other vertex, then we can estimate that E ≈ V ∗ V (actually E = V ∗ (V − 1)/2), which implies that time complexity is O(V ∗ E) = O(V^3 ).

We now consider a more accurate analysis of BFS. Clearly, we do not need to explore all edges in the graph for each vertex. Instead, for each vertex v we only explore the adjacent edges for this vertex which is some number Adj v . The more precise analysis breaks Search(Lines 6 : 12) by looking at the time spent to process each vertex during its Finish and Explore steps. Here is the while loop, unwound to show the time spent per vertex:

Even though we do not know the individual terms in the above summation we actually know the overall value of the summation is 2E, since every time we look at an adjacent vertex we effectively look at one of the edges (a, b), so each edge (a, b) is looked at twice — once from the point of view of vertex a and once from the point of view of vertex b. Finally, we get