# Depth-First Search in Python

Fariba Laiq Oct 10, 2023

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.