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

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.

## No comments:

Post a Comment