Introduction
Depthfirst search (DFS) is an algorithm for traversing or searching tree or graph data structures. The DFS Algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
A version of the depthfirst search was investigated in the 19th century by French mathematician Charles Pierre Tremaux as a strategy for solving mazes.
Example:
A depthfirst search starting at A, assuming that the left edges in the shown graph are chosen before right edges, and assuming the search remembers previously visited nodes and will not repeat them (since this is a small graph), will visit the nodes in the following order: A, B, D, F, E, C, G.
The edges traversed in this search form a Trémaux tree, a structure with important applications in graph theory. Performing the same search without remembering previously visited nodes results in visiting nodes in the order A, B, D, F, E, A, B, D, F, E, etc. forever, caught in the A, B, D, F, E cycle and never reaching C or G. Iterative deepening is one technique to avoid this infinite loop and would reach all nodes.
Output of a DepthFirst Search: A convenient description of a depthfirst search of a graph is in terms of a spanning tree of the vertices reached during the search. Based on this spanning tree, the edges of the original graph can be divided into three classes: forward edges, which point from a node of the tree to one of its descendants, back edges, which point from a node to one of its ancestors, and cross edges, which do neither. Sometimes tree edges, edges which belong to the spanning tree itself, are classified separately from forwarding edges. If the original graph is undirected then all of its edges are tree edges or back edges.
DFS Algorithm
A standard DFS implementation puts each vertex of the graph into one of two categories:

Visited

Not Visited
The purpose of the algorithm is to mark each vertex as visited while avoiding cycles.
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.
Pseudocode
DFSiterative (G, s): //Where G is graph and s is source vertex
let S be stack
S.push( s ) //Inserting s in stack
mark s as visited.
while ( S is not empty):
//Pop a vertex from stack to visit next
v = S.top( )
S.pop( )
//Push all the neighbours of v in stack that are not visited
for all neighbours w of v in Graph G:
if w is not visited :
S.push( w )
mark w as visited
DFSrecursive(G, s):
mark s as visited
for all neighbours w of s in Graph G:
if w is not visited:
DFSrecursive(G, w)