Depth First Search:

The general idea behind depth first traversal is that, starting from any random vertex, single path is traversed until a vertex is found whose all the neighbors are already been visited. The search then backtracks on the path until a vertex with unvisited adjacent vertices is found …