Breadth-first search

Breadth-first search

BFS(G,s)
for each vertex in graph (u) except source vertex (s)
  u.color = white
  u.d = infinte
  u.a = nil
s.color = gray
s.d = 0
s.a = nil

Q = 0            //create an empty queue
Enqueue(Q)
while Q!=null
  u = Dequeue(Q)
  for each v in adjacent[u]
    if v.color = white
      v.color = gray
      v.d = v.d + 1
      v.a = u
      Enqueue(Q,v)
u.color = Black