BFS- Breadth First Search

Procedure BFS (G, S)

The above Procedure computes the breadth-first-search for a given graph ‘G’. Variable ‘S’ refers to the start of graph ‘G’. Three arrays color [u] holds the color of u, pre [u] points to the predecessor of u, and dist [u] calculates the distance from S to u. The subalgorithms Enqueue and Dequeue are also used for inserting and deleting element from the queue.

Step 1 Initialization, loop

for u ¬ V1, V2, ..... R For each u in V

{

set color [u] ¬ white

set dist [u] ¬ ¥

set pre [u] ¬ NULL

}

Step 2 Intializing source S, placing ‘S’ in the queue

set color [S] ¬ gray

set dist [S] ¬ 0

set Q ¬ {S} R putting S in the queue

Step 3 Loop, while no more adjacent vertices

while (Q ¹ NULL)

{

set u ¬ Dequeue (Q) R u is the next to visit

for V ¬ Vk .... Vn R for each V in adj [u]

{

if (color [V] = white) then { R if neighbour unreached

set color [V] ¬ gray R mark it reached

set dist [V] ¬ dist [u] + 1 R set its distance

set pre [V] ¬ u R set its predecessor

call to Enqueue (Q, V) R put in the queue

}

set color [u] ¬ black R u is visited

}

Step 4 Return at the point of call

return.