# Depth-First Search in Python

The depth-first search is an algorithm for traversing a `tree` or a `graph`. In `DFS`, traversing starts from the root node and goes deeper and deeper.

It performs `backtracking` and upward when it reaches the leaf node.

Depth First Search is used in many applications like:

• Detecting cycle in a graph
• `Path Finding`
• `Travelling-Salesman` Problem

## Depth First Search Example Using a `Graph` in Python

We have six vertices, `1` is the root vertex. We will traverse `1`, then it has two adjacent vertices `5 and 9`, so first, we will traverse its left vertex, and then we will traverse the adjacent vertex of `5`.

When finding a leaf node, we will backtrack and repeat the same procedure to recent unvisited nodes.

In this example, `green` vertices are the traversed ones, and `red` is the not yet traversed ones.

## Depth First Search Using `Recursion` in Python

The `recursion` technique calls the `DFS` function. The base condition is `true` when traversing all the graph’s vertices.

The following code uses a `dictionary data` structure to represent an `adjacency list` to store a graph in memory.

We will declare a set to keep track of all the vertices we have `visited`.

If the vertex is not traversed, we traverse it first by printing it and adding it to the traversed set.

``````# Python 3.x
graph = {
'1' : ['5','9'],
'5' : ['2', '4'],
'9' : ['8'],
'2' : ['4'],
'4' : ['2'],
'8' : []
}
traversed = set()
def dfs(traversed, graph, vertex):
if vertex not in traversed:
print (vertex)
print("Depth First Search:")
dfs(traversed, graph, '1')
``````

Output:

``````# python 3.x
Depth First Search:
1
5
2
4
9
8
``````

We had to go deeper and deeper by traversing the `adjacent vertex` of the graph and performing DFS.

We backtracked, visited the most recent unvisited vertices, and performed DFS for that vertex.

In the driver code, we had to call the `dfs` function and specify the `root vertex`, `1` in our case.

## Depth First Search Using `Iteration` in Python

Use a loop to iterate over the graph’s vertices. We will also use a `stack` to keep track of `unvisited` vertices.

First, we will traverse the `root node` and push it into the `stack`. Then while our stack is not empty, we will `peek` (read topmost most vertex without removing it) a vertex from the stack, and if that vertex is not traversed, we will traverse it.

Then we will read the `adjacent vertex` of the vertex we just traversed and push it into the stack if we have not traversed it before.

``````#Python 3.x
def dfs(graph, root_node):
traversed = [root_node]
stack = [root_node]
while stack:
vertex = stack[-1]
if vertex not in traversed:
traversed.extend(vertex)
pop = True
pop = False
break
if pop:
stack.pop()
return traversed
graph = {
'1' : ['5','9'],
'5' : ['2', '4'],
'9' : ['8'],
'2' : ['4'],
'4' : ['2'],
'8' : []
}
print (dfs(graph, '1'))
``````

Output:

``````#python 3.x
['1', '5', '2', '4', '9', '8']
``````

We had to go deeper and deeper and reach the `leaf node` with no adjacent vertices. We had pop `leaf nodes` from the `stack` because DFS will not be performed, and we have already traversed it.

So, the `for` loop does has not been executed. We will backtrack.

The control goes again in the `while` loop, and DFS performed for the peek element of the stack until the `stack` is empty.

Author: Fariba Laiq

I am Fariba Laiq from Pakistan. An android app developer, technical content writer, and coding instructor. Writing has always been one of my passions. I love to learn, implement and convey my knowledge to others.