= BFS =

BFS uses a coloring scheme and queue to search nodes in a graph. The algorithm works like this: Give a Graph G and a starting node s.

== Algorithm ==

   1 Color all the nodes white
   1 Set the distance for each node u to be d[u]= ∞
   1 Set the parent of each node u to be [u]=nil
   1 Color s grey
   1 Enqueue s → Q
   1 while Q is not empty
   1 u=dequeue(Q)
   1 find each white neighbor v of u do
   1 d[v]=d[u]+1
   1 [v]=u
   1 enqueue(v)
   1 color[u]=black

== Properties ==

   * '''Running time for BFS is O(V+E)'''
   * BFS finds only those vertices that are reachable from s.
   * The graph created from a BFS has '''no cycles'''

'''Theorem:''' ''The BFS values stored in d[u] give the length of the shortest path from s->u.''


'''Proof''': Our inductive hypothesis is

	d[v]=(s,v) for all v ∈ V 

We can prove this based on the number of equeue operations and the assignment of 
d[v]=d[u]+1 in line 9 above. Let (s,v) be the shortest path from s→v. The base 
case is d[s]=0=(s,s).

For the inductive step, consider a white vertex v that is discovered during the 
search from a vertex u. The inductive hypothesis impleys that

	d[u]=(s,u)

From the assignment in line 9 we have

        d[v] = d[u]+1
	 
             = (s,u)+1

             = (s,v)

since v is never enqueued again and hence d[v] never changes again, the inductive 
hypothesis is maintained. Thus we conclude that BFS finds the shortest path from 
s->v, for v∈V.