Running time of Breath-First-Search — Proof

Running time of Breath-First-Search is (V+E), where V — number of vertexes and E — number of edges.

Pseudocode for BFS.

· Enqueue and dequeue operations take O(1) time, so the total time for queuing is O(V).

· Since each adjacency list is explored at most once the sum of all the adjacency list is O(E). So the total time for exploring adjacency lists is O(E).

Therefore the total running time of BFS is O(V+E).