Depth First Search (DFS): Concept, Implementation, Advantages, Disadvantages

Depth First Search (DFS)

DFS is also an important type of uniform search. DFS visits all the vertices in the graph. This type of algorithm always chooses to go deeper into the graph. After DFS visited all the reachable vertices from a particular sources vertices it chooses one of the remaining undiscovered vertices and continues the search. DFS reminds the space limitation of breath first search by always generating next a child of the deepest unexpanded nodded. The data structure stack or last in first out (LIFO) is used for DFS. One interesting property of DFS is that, the discover and finish time of each vertex from a parenthesis structure. If we use one open parenthesis when a vertex is finished then the result is properly nested set of parenthesis.

Concept:

Step 1: Traverse the root node.

Step 2: Traverse any neighbour of the root node.

Step 3: Traverse any neighbour of neighbour of the root node.

Step 4: This process will continue until we are getting the goal node.

Algorithm:

Step 1: PUSH the starting node into the stack.

Step 2: If the stack is empty then stop and return failure.

Step 3: If the top node of the stack is the goal node, then stop and return success.

Step 4: Else POP the top node from the stack and process it. Find all its neighbours that are in ready state and PUSH them into the stack in any order.

Step 5: Go to step 3.

Step 6: Exit.

Implementation:

Let us take an example for implementing the above DFS algorithm.

Consider A as the root node and L as the goal node in the graph figure

Step 1: PUSH the starting node into the stack i.e.

Also you can traverse the graph starting from the root A and then insert in the order C and B into the stack. Check your answer.

Advantages:

DFSconsumes very less memory space.

It will reach at the goal node in a less time period than BFS if it traverses in a right path.

It may find a solution without examining much of search because we may get the desired solution in the very first go.

Disadvantages:

It is possible that may states keep reoccurring. There is no guarantee of finding the goal node.

Sometimes the states may also enter into infinite loops.