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