Saturday, June 14, 2008

DFS- Depth First Search

Procedur DFS (G)

The above Procedure computes the depth-first-search of the given ‘G’ graph ‘G’. It takes the advantage of Procedure DFS visit ( ). All the auxillary arrays used in this procedure have been previously described.

Step 1 Loop, intialization
for u  V1, V2 .... Vn R for each u in V
set color [u]  white
set pre [u]  NULL
Step 2 Setting time
set time  0
Step 3 Loop, finding unreached vertex and start new search
for u  V1, V2 .... V R for each u in V
if (color = white) R found unreached vertex
call to DFS visit (u) R start a new search
Step 4 Return at point of call

No comments: