Depth First Search in Graphs

http://install4install.com

DFS technique is used to traverse graphs.Any vertex is chosen as the starting vertex .Element is pushed into stack.One adjacent vertex is randomly picked from adjacent vertices.It is marked and pushed it into stack.If adjacent unvisited neighbors are present then same process is followed otherwise element is popped off from the stack.Now,again one element is picked as the unvisited adjacent  element and marked.Same process if followed till all the vertices are visited.

Example

Consider graph in Fig 1.We need to perform DFS on it.

Screen Shot 2014-07-15 at 5.09.35 PM

Fig 1 : A Graph

 

Screen Shot 2014-07-16 at 1.26.21 PM

Fig 2 : Mark A

Screen Shot 2014-07-16 at 2.10.30 PM

Fig 3 : Push A

 

 

 

 

 

 

 

 

 

 

 

1

Fig 4 : Mark B

 

Screen Shot 2014-07-16 at 2.20.52 PM

Fig 5 : Push B

 

Screen Shot 2014-07-16 at 2.23.45 PM

Fig 6 : Mark C

Screen Shot 2014-07-16 at 2.24.25 PM

Fig 7 : Push C

 

Screen Shot 2014-07-16 at 2.28.08 PM

Fig 8 : Mark D

Screen Shot 2014-07-16 at 2.29.06 PM

Fig 9 : Push D

 

 

Screen Shot 2014-07-16 at 2.32.47 PM

Fig 10 : Mark E

Screen Shot 2014-07-16 at 2.33.24 PM

Fig 11 : Push E

 

Screen Shot 2014-07-16 at 2.35.42 PM

Fig 12 : Mark G

Screen Shot 2014-07-16 at 2.37.05 PM

Fig 13 : Push G

Screen Shot 2014-07-16 at 2.38.32 PM

Fig 14 : Mark F

 

Screen Shot 2014-07-16 at 2.41.21 PM

Fig 15 : Push F

 

Screen Shot 2014-07-16 at 2.37.05 PM

Fig 16 : Pop F

Screen Shot 2014-07-16 at 2.33.24 PM

Fig 17 : Pop G

Screen Shot 2014-07-16 at 2.24.25 PM

Fig 18 : Pop C

Screen Shot 2014-07-16 at 2.20.52 PM

Fig 19 : Pop C

Screen Shot 2014-07-16 at 3.31.31 PM

Fig 20 : Pop B

Screen Shot 2014-07-16 at 3.31.58 PM

Fig 21 : Pop A

 

 

 

 

 

 

 

 

 

 



Short URL: http://tinyit.cc/d9f0cd
Author: Cusp2207 on July 16, 2014
Category: Computer Science
Tags:

Leave a Reply

Last articles