# 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.

• Pick any random vertex.Say A.
• Visit A and mark it.(Fig 2)
• Result Sequence--> A
• Push A to the stack.(Fig 3)
• 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

• 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

• 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

• 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)

• 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)
• Mark F and add to the stack(Fig 14,15)

• 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.

Rate this post