Breadth First Search (BFS)
BFS(V, E, s)
1. for each u in V − {s} ▷ for each vertex u in V[G] except s.
2. do color[u] ← WHITE
3. d[u] ← infinity
4. π[u] ← NIL
5. color[s] ← GRAY ▷ Source vertex discovered
6. d[s] ← 0 ▷ initialize
7. π[s] ← NIL ▷ initialize
8. Q ← {} ▷ Clear queue Q
9. ENQUEUE(Q, s)
10 while Q is nonempty
11. do u ← DEQUEUE(Q) ▷ That is, u = head[Q]
12. for each v adjacent to u ▷ for loop for every node along with edge.
13. do if color[v] ← WHITE ▷ if color is white you’ve never seen it before
14. then color[v] ← GRAY
15. d[v] ← d[u] + 1
16. π[v] ← u
17. ENQUEUE(Q, v)
18. DEQUEUE(Q)
19. color[u] ← BLACK
Example: The following figure (from CLRS) illustrates the progress of breadthfirst search on the undirected sample graph.
a. After initialization (paint every vertex white, set d[u] to infinity for each vertex u, and set the parent of every vertex to be NIL), the source vertex is discovered in line 5. Lines 89 initialize Q to contain just the source vertex s.
b. The algorithm discovers all vertices 1 edge from s i.e., discovered all vertices (w and r) at level 1.
c.
d. The algorithm discovers all vertices 2 edges from s i.e., discovered all vertices (t, x, and v) at level 2.
e.
f.
g. The algorithm discovers all vertices 3 edges from s i.e., discovered all vertices (u and y) at level 3.
h.
i. The algorithm terminates when every vertex has been fully explored.
Analysis

The whileloop in breadthfirst search is executed at most V times. The reason is that every vertex enqueued at most once. So, we have O(V).

The forloop inside the whileloop is executed at most E times if G is a directed graph or 2E times if G is undirected. The reason is that every vertex dequeued at most once and we examine (u, v) only when u is dequeued. Therefore, every edge examined at most once if directed, at most twice if undirected. So, we have O(E).
Therefore, the total running time for breadthfirst search traversal is O(V + E).