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:
Reference : Introduction to Algorithms by Corman, Leiserson & Rivest (MIT Press)