DepthFirst Search in Python

Depth First Search Example Using a
Graph
in Python 
Depth First Search Using
Recursion
in Python 
Depth First Search Using
Iteration
in Python
The depthfirst 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
TravellingSalesman
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)
traversed.add(vertex)
for adjacent in graph[vertex]:
dfs(traversed, graph, adjacent)
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
for adjacent in graph[vertex]:
if adjacent not in traversed:
stack.extend(adjacent)
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.
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.
LinkedIn