What is the time complexity of BFS (Breadth-First Search) in terms of V…

BFS explores each vertex and edge exactly once using a queue. For V vertices and E edges, this results in O(V + E) time complexity.

Note (For More Understanding)
Here is a detailed explanation of why O(V + E) is the exact time complexity for Breadth-First Search (BFS) when using an adjacency list:

1. Vertex Exploration: O(V)

In BFS, we use a boolean array or set (typically called visited) to keep track of the vertices we have already processed.

• A vertex is only pushed into the FIFO (First-In, First-Out) queue if its visited status is false.

• Once it enters the queue, it is marked as visited = true, ensuring it can never enter the queue a second time.

• Enqueuing and dequeuing a vertex takes constant time, O(1)

• Since there are V vertices, managing the queue across the entire lifetime of the algorithm takes O(V) time.

2. Edge Exploration: O(E)

When a vertex is popped out of the queue, the algorithm looks at all of its adjacent neighbors to see if they need to be visited.

• If the graph is represented as an Adjacency List, the algorithm only loops through the actual neighbors connected to that specific vertex.

• In a Directed Graph, every single edge is looked at exactly once during the entire execution.

• In an Und undirected Graph, every edge is looked at exactly twice (once from each of the two vertices it connects).

• Therefore, the total time spent scanning neighbor lists across the entire run is proportional to the total number of edges, giving us O(E) time.

Putting It Together

Because the queue management and edge lookups happen in tandem, we add the two components together. This results in a final linear time complexity of:

Total Time Complexity = O(V + E)

Why it isn't O(V x E): The algorithm doesn't look at all E edges for every vertex. Instead, the total work of looking at edges is distributed across all vertices. Once an edge's origin vertex is done, that edge is never scanned again.