# Explain what is DFS (Depth First Search) algorithm for a Graph and how does it work?

Technology CommunityCategory: BacktrackingExplain what is DFS (Depth First Search) algorithm for a Graph and how does it work?
VietMX Staff asked 12 months ago

Depth First Traversal or Depth First Search is a edge based recursive algorithm for traversing (visiting) all the vertices of a graph or tree data structure using a stack. The purpose of the algorithm is to mark each vertex as visited while avoiding cycles. DFS traverse/visit each vertex exactly once and each edge is inspected exactly twice. DFS is a genuinely recursive algorithm that uses stack for backtracking purposes, not for storing the vertex discovery “front” (as is the case in BFS).

The DFS algorithm works as follows:

• Start by putting any one of the graph’s vertices on top of a stack.
• Take the top item of the stack and add it to the visited list.
• Create a list of that vertex’s adjacent nodes. Add the ones which aren’t in the visited list to the top of the stack.
• Keep repeating steps 2 and 3 until the stack is empty.

DFS example step-by-step:

• Considering A as the starting vertex which is explored and stored in the stack.
• B successor vertex of A is stored in the stack.
• Vertex B have two successors E and F, among them alphabetically E is explored first and stored in the stack.
• The successor of vertex E, i.e., G is stored in the stack.
• Vertex G have two connected vertices, and both are already visited, so G is popped out from the stack.
• Similarly, E s also removed.
• Now, vertex B is at the top of the stack, its another node(vertex) F is explored and stored in the stack.
• Vertex F has two successor C and D, between them C is traversed first and stored in the stack.
• Vertex C only have one predecessor which is already visited, so it is removed from the stack.
• Now vertex D connected to F is visited and stored in the stack.
• As vertex D doesn’t have any unvisited nodes, therefore D is removed.
• Similarly, F, B and A are also popped.
• The generated output is – A, B, E, G, F, C, D.