# 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)