Facebook

Depth First Search in Graphs

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

 

  • Pick any random vertex.Say A.
  • Visit A and mark it.(Fig 2)
  • Result Sequence--> A
Screen Shot 2014-07-16 at 1.26.21 PM
Fig 2 : Mark A
  • Push A to the stack.(Fig 3)
Screen Shot 2014-07-16 at 2.10.30 PM
Fig 3 : Push A
  • Find the neighbors of A.
  • E,B,D are neighbors of A.
  • Pick random vertex.Say B.
  • Mark B.(Fig 4)
  • Push B to the stack.(Fig 5)
  • Result Sequence --> AB
1
Fig 4 : Mark B

 

Screen Shot 2014-07-16 at 2.20.52 PM
Fig 5 : Push B

 

  • Look for adjacent unvisited neighbors of B.
  • C is the neighbor.
  • Visit C and mark it.(Fig 6)
  • Push C to the stack.(Fig 7)
  • Result Sequence --> ABC
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

 

  • Look for neighbors of C.
  • E and D are neighbors.
  • Say we mark D.(Fig 8)
  • Push D to the stack.(Fig 9)
  • Result Sequence --> ABCD
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

 

  • Look for adjacent unvisited vertices of D.
  • There are no adjacent unvisited vertices.
  • Pop D and look for adjacent vertices of C.
  • E is the adjacent unvisited vertex.
  • Mark E.(Fig 10)
  • Push E to the stack.(Fig 11)

 

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

 

  • Look for adjacent unvisited vertices of E.
  • G and F are the vertices.
  • Say G is chosen.
  • Visit G and mark it.(Fig 12)
  • Push G to the stack.(Fig 13)
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
  • Mark F and add to the stack(Fig 14,15)
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

 

  • No other unvisited adjacent element of F is present.
  • So,POP F.
  • Same is the case with other vertices.
  • So Pop all vertices one by one.
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

 

 

 

 

 

 

 

 

 

 

Rate this post

Comments

So empty here ... leave a comment!

Leave a Reply

Your email address will not be published. Required fields are marked *

Sidebar