Thank you for printing our content at [Link].

Please check back soon for new

contents.

Learn to code efficiently ([Link]

36%
off
with DSA Learn with utm_source=sticky-
Programiz PRO banner&utm_campaign=programiz&utm_medium=referral)
([Link]
Programiz
PRO
utm_source=nav-
Search tutorials & examples
(/)
floating&utm_campaign=programiz&utm_medium=referral)
[Link]

Depth First Search (DFS)

Depth first Search or Depth first traversal is a recursive
algorithm for searching all the vertices of a graph or tree
data structure. Traversal means visiting all the nodes of a
graph (/dsa/graph).

Depth First Search Algorithm

A standard DFS implementation puts each vertex of the
graph into one of two categories:

1. Visited

2. Not Visited

The purpose of the algorithm is to mark each vertex as

visited while avoiding cycles.

The DFS algorithm works as follows:

1. Start by putting any one of the graph's vertices on top

of a stack.
 2. Take
Thank you for printing ourthe top item
content of the stack and addPlease
at [Link]. it to the visited
check back soon for new
contents.
list.
Learn to code efficiently ([Link]
36% 3. Create
with DSA Learn with
a list of that vertex's adjacent nodes. Add the
utm_source=sticky-
off
ones which aren't in
Programiz PRO the visited list to the top of the
banner&utm_campaign=programiz&utm_medium=referral)
([Link]
stack.
Programiz
utm_source=nav-
Search tutorials & examples
PRO (/)
floating&utm_campaign=programiz&utm_medium=referral)
4. Keep [Link]
steps 2 and 3 until the stack is empty.

Depth First Search Example

Let's see how the Depth First Search algorithm works with
an example. We use an undirected graph with 5 vertices.

Undirected graph with 5 vertices

We start from vertex 0, the DFS algorithm starts by putting

it in the Visited list and putting all its adjacent vertices in
the stack.

Visit the element and put it in the visited list

 Next,our
Thank you for printing wecontent
visit theatelement at the top of stack
[Link]. [Link]
Please 1 andback
go soon for new
contents. to its adjacent nodes. Since 0 has already been visited,
Learn towe visit
code 2 instead.
efficiently ([Link]
36%
off
with DSA Learn with utm_source=sticky-
Programiz PRO banner&utm_campaign=programiz&utm_medium=referral)
([Link]
Programiz
PRO
utm_source=nav-
Search tutorials & examples
(/)
floating&utm_campaign=programiz&utm_medium=referral)
[Link]

Visit the element at the top of stack

Vertex 2 has an unvisited adjacent vertex in 4, so we add

that to the top of the stack and visit it.
Thank you for printing our2content
Vertex at [Link].
has an unvisited adjacent vertex in 4, so Please check
we add that back soon for new
to the
contents. top of the stack and visit it.

Learn to code efficiently ([Link]

36%
off
with DSA Learn with utm_source=sticky-
Programiz PRO banner&utm_campaign=programiz&utm_medium=referral)
([Link]
Programiz
PRO
utm_source=nav-
Search tutorials & examples
(/)
floating&utm_campaign=programiz&utm_medium=referral)
[Link]

Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the

top of the stack and visit it.

After we visit the last element 3, it doesn't have any

unvisited adjacent nodes, so we have completed the
Depth First Traversal of the graph.

After we visit the last element 3, it doesn't have any unvisited

adjacent nodes, so we have completed the Depth First Traversal of
the graph.

DFS Pseudocode (recursive

implementation)
The pseudocode for DFS is shown below. In the init()
function, notice that we run the DFS function on every
node. This is because the graph might have two different
 disconnected
Thank you for printing parts
our content so to make sure that we
at [Link]. cover
Please every
check back soon for new
contents. vertex, we can also run the DFS algorithm on every node.
Learn to code efficiently ([Link]
36%
off
with DSA Learn
DFS(G,withu) utm_source=sticky-
Programiz PRO [Link] = true banner&utm_campaign=programiz&utm_medium=referral)
([Link]
Programiz for each v ∈ [Link][u]
PRO
utm_source=nav-
Search tutorials & examples
(/) if [Link] == false
floating&utm_campaign=programiz&utm_medium=referral)
DFS(G,v)
[Link]

init() {
For each u ∈ G
[Link] = false
For each u ∈ G
DFS(G, u)
}

DFS Implementation in Python, Java

and C/C++
The code for the Depth First Search Algorithm with an
example is shown below. The code has been simplified so
that we can focus on the algorithm rather than other
details.

Python Java C C++

Thank you for printing our content at [Link]. Please check back soon for new
contents.
# DFS algorithm in Python

Learn to code efficiently ([Link]

36%
with DSA Learn with utm_source=sticky-
off # DFS algorithm
Programiz PRO banner&utm_campaign=programiz&utm_medium=referral)
def([Link]
dfs(graph, start, visited=None):
Programiz if visited is None:
PRO
utm_source=nav-
Search tutorials & examples
(/) visited = set()
floating&utm_campaign=programiz&utm_medium=referral)
[Link](start)
[Link]

print(start)

for next in graph[start] - visited:

dfs(graph, next, visited)
return visited

graph = {'0': set(['1', '2']),

'1': set(['0', '3', '4']),
'2': set(['0']),
'3': set(['1']),
'4': set(['2', '3'])}

dfs(graph, '0')

Complexity of Depth First Search

The time complexity of the DFS algorithm is represented in
the form of O(V + E) , where V is the number of nodes
and E is the number of edges.

The space complexity of the algorithm is O(V) .

Application of DFS Algorithm

1. For finding the path

2. To test if the graph is bipartite

3. For finding the strongly connected components of a

graph
 4. Forour
Thank you for printing detecting cycles
content at in a graph
[Link]. Please check back soon for new
contents.

Learn to code efficiently ([Link]

36%
off
with DSA Learn with utm_source=sticky-
Programiz PRO banner&utm_campaign=programiz&utm_medium=referral)
([Link]
Programiz
PRO
utm_source=nav-
Search tutorials & examples
(/)
floating&utm_campaign=programiz&utm_medium=referral)
[Link]

Next Tutorial:
(/dsa/graph-bfs)
Breadth-first Search

Previous Tutorial:
(/dsa/graph-adjacency-list)
Adjacency List

Share on:

([Link] ([Link]
u=[Link] text=Check%20this%2
dfs)

Did you find this article helpful?

 Our
Thank you for printing premium
our content atlearning platform, created
[Link]. with back soon for new
Please check
contents.
over a decade of experience.
Learn to code efficiently ([Link]
36%
with DSA Learn with utm_source=sticky-
off Try Programiz PRO
Programiz PRO banner&utm_campaign=programiz&utm_medium=referral)
([Link]
([Link]
Programizutm_source=tutorial-
PRO
utm_source=nav-
Search tutorials & examples
(/) banner-
floating&utm_campaign=programiz&utm_medium=referral)
[Link]
bottom&utm_campaign=programiz&utm_medium=referral)

Related Tutorials

DS & Algorithms

Breadth first search

(/dsa/graph-bfs)

DS & Algorithms

Adjacency List

(/dsa/graph-adjacency-list)

DS & Algorithms

Strongly Connected Components

(/dsa/strongly-connected-components)

DS & Algorithms

Graph Data Stucture

(/dsa/graph)