Breath first search

Input G = (V,E) is represented using adjacency list.  color[u] stored the color ot u in V.  pi[u] stored the predecessor of u.  d[u] stored the distance from source s to the vertex u.  Q is a first-in-first-out queue to manage the set of gray vertices.

BFS(G,s)
1 for each vertex u in V[G] – {s}
2   do color[u] = white
3      d[u] = inf
4      pi[u] = NIL
5 color[s] = GRAY
6 d[s] = 0
7 pi[s] = NIL
8 Q = {s}
9 while Q != empty
10   do u = head[Q]
11     for each v in Adj[u]
12       do if color[v] = WHITE
13            then color[v] = GRAY
14                 d[v] = d[u] + 1
15                 pi[v] = u
16                 Enqueue(Q,v)
17     Dequeue(Q)
18     color[u] = BLACK