Depth first search

What is searching ?

Searching is finding any information from a set of data stored in the form of elements in computer memory. The data is in different forms like an array, tree, graph, linked list, etc. Every type requires a different searching method. The types of searching are as follows :

  1. Linear search
  2. Binary search
  3. Depth first search
  4. Breadth first search

Depth first search

This searching method is also the same as depth-first traversal for trees; just the difference is the graph may contain cycles, and the tree doesn’t. This algorithm starts from the root, tries to reach every node, and avoids visiting the same node again while traversing. Stack is used here as the data structure. In DFS, the traversing is done until we find the goal node.

  1. Create a recursive function that will point to the node and visited array also
  2. Mark the current node as visited and print it.
  3. Visit all the unvisited nodes and call the function.

The complexity is O(V+E), where V is the number of vertices and E is the number of edges.

Space Complexity: O(V) is the space complexity.

Advantages

  • It consumes very less memory
  • It reaches the goal node in a very short period.