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.