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

## Comments

So empty here ... leave a comment!