# Depth First Search (DFS) – Iterative and Recursive Implementation Depth–first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root for a graph) and explore as far as possible along each branch before backtracking.

The following graph shows the order in which the nodes are discovered in DFS: ### Depth–first search in trees

A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any acyclic connected graph is a tree. For a tree, we have the following traversal methods:

These are already covered in detail in separate posts.

### Depth–first search in Graph

A Depth–first search (DFS) is a way of traversing graphs closely related to the preorder traversal of a tree. Following is the recursive implementation of preorder traversal:

procedure preorder(treeNode v)
{
visit(v);
for each child u of v
preorder(u);
}

To turn this into a graph traversal algorithm, replace “child” with “neighbor”. But to prevent infinite loops, keep track of the vertices that are already discovered and not revisit them.

procedure dfs(vertex v)
{
visit(v);
for each neighbor u of v
if u is undiscovered
call dfs(u);
}

The recursive algorithm can be implemented as follows in C++, Java, and Python:

## C++

Output:

0 1 2 3 4 5 6 7 8 9 10 11 12

## Java

Output:

0 1 2 3 4 5 6 7 8 9 10 11 12

## Python

Output:

0 1 2 3 4 5 6 7 8 9 10 11 12

The time complexity of DFS traversal is O(V + E), where `V` and `E` are the total number of vertices and edges in the graph, respectively. Please note that O(E) may vary between O(1) and O(V2), depending on how dense the graph is.

## Iterative Implementation of DFS

The non-recursive implementation of DFS is similar to the non-recursive implementation of BFS but differs from it in two ways:

• It uses a stack instead of a queue.
• The DFS should mark discovered only after popping the vertex, not before pushing it.
• It uses a reverse iterator instead of an iterator to produce the same results as recursive DFS.

Following is the C++, Java, and Python program that demonstrates it:

## C++

Output:

0 1 2 3 4 5 6 7 8 9 10 11 12

## Java

Output:

0 1 2 3 4 5 6 7 8 9 10 11 12

## Python

Output:

0 1 2 3 4 5 6 7 8 9 10 11 12

## Applications of DFS

Also See:

Depth First Search (DFS) – Interview Questions & Practice Problems

Rate this post

Average rating 4.8/5. Vote count: 403

No votes so far! Be the first to rate this post.

We are sorry that this post was not useful for you!

Tell us how we can improve this post? 