Description

Given a graph G=(V,E) and a source vertex s, BFS systematically explores the edges of E to disover every vertex that is reachable from s.
It computes the distance (smallest no. of edges) from s to each reachable vertex. It produces a BFS tree with root s that contains all reachable vertices.
For any vertex v reachable from s, the path in the BFS tree from s to v corr. to a shortest path from s to v in G, i.e. path containing the smallest number of edges. BFS discovers all vertices at distance k from s before discovering any vertices at distance k+1.

Implementation

The pseudocode below assumes that the input graph G = (V,E) is represented using adjacency lists. It maintains several additional data fields with each vertex in the graph.
The color of each vertex u in V is stored in color[u], and the predecessor of u is stored in prev[u]. If u has no predecessor, then prev[u] = NULL. The distance from the source s to vertex u is stored in dist[u] . The algorithm uses a FIFO queue Q to manage the set of gray vertices.

Pseudocode

BFS(G,s)
1   for each vertex u in V[G] - {s}
2     do color[u] <-- WHITE
3         dist[u] <-- INF
4         prev[u] <-- NULL
5   color[s] <-- GRAY
6   dist[s] <-- 0
7   prev[s] <-- NULL
8   Q <-- {}
9   ENQUEUE(Q, s)
10 while Q!={}
11    do u <-- DEQUEUE(Q)
12      foreach v in Adj[u]
13         do if color[v]=WHITE
14              then color[v] <-- GRAY
15                  dist[v] <-- d[u] +1
16                  prev[v] <-- u
17                  ENQUEUE(Q,v)
18      color[u] <-- BLACK

Analysis

Total running time is: O(V+E). BFS runs linear in the size of the adjacency list representation of the graph G.

Source code:

BFS.py

Reference :  Introduction to Algorithms by Corman, Leiserson & Rivest (MIT Press)