Time Complexity of Breadth First Search (BFS)

Best Case: O(V + E)

• The best-case time complexity of BFS occurs when the target node is found after exploring only a few vertices and edges.
• In this case, the algorithm may terminate early without having to visit all vertices and edges.
• Thus, the time complexity is O(V + E), where V is the number of vertices and E is the number of edges.

Average Case: O(V + E)

• The average-case time complexity of BFS is also O(V + E).
• This complexity holds true across various graph structures and densities.
• BFS typically explores vertices and edges in a breadth-first manner, which results in a linear time complexity proportional to the sum of vertices and edges.

Worst Case: O(V + E)

• The worst-case time complexity of BFS also remains O(V + E).
• In the worst case, BFS explores all vertices and edges reachable from the source node.
• The algorithm systematically visits each vertex and edge in a breadth-first manner, ensuring all reachable nodes are discovered.
• Therefore, the time complexity is O(V + E) as it traverses all vertices and edges in the graph.