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.

what-is-DFS-depth-first-search-algorithm