Depth First Search algorithm in Python (Multiple Examples)

Depth First Search is a popular graph traversal algorithm. In this tutorial, We will understand how it works, along with examples; and how we can implement it in Python.
We will be looking at the following sections:

Introduction

Graphs and Trees are one of the most important data structures we use for various applications in Computer Science.
They represent data in the form of nodes, which are connected to other nodes through ‘edges’.

The Depth First Search Algorithm

Depth First Search begins by looking at the root node (an arbitrary node) of a graph. If we are performing a traversal of the entire graph, it visits the first child of a root node, then, in turn, looks at the first child of this node and continues along this branch until it reaches a leaf node.

Representing a graph

Before we try to implement the DFS algorithm in Python, it is necessary to first understand how to represent a graph in Python.

Adjacency Matrix

Adjacency Matrix is a square matrix of shape N x N (where N is the number of nodes in the graph).
Each row represents a node, and each of the columns represents a potential child of that node.
Each (row, column) pair represents a potential edge.

Adjacency List

Adjacency List is a collection of several lists. Each list represents a node in the graph, and stores all the neighbors/children of this node.

graph = {"A": ["B", "C"], "B": ["C"], "C": ["D"]}

Implementing Depth First Search(a non-recursive approach)

We will consider the graph example shown in the animation in the first section.

graph = {"A":["D","C","B"], "B":["E"], "C":["G","F"], "D":["H"], "E":["I"], "F":["J"]}
def dfs_non_recursive(graph, source):

if source is None or source not in graph:

return "Invalid input"

path = []

stack = [source]

while(len(stack) != 0):

s = stack.pop()

if s not in path:

path.append(s)

if s not in graph:

#leaf node
continue

for neighbor in graph[s]:

stack.append(neighbor)

return " ".join(path)
DFS_path = dfs_non_recursive(graph, "A") 
print(DFS_path)

DFS using a recursive method

We can implement the Depth First Search algorithm using a popular problem-solving approach called recursion.

def recursive_dfs(graph, source,path = []):

if source not in path:

path.append(source)

if source not in graph:
# leaf node, backtrack
return path

for neighbour in graph[source]:

path = recursive_dfs(graph, neighbour, path)


return path
graph = {"A":["B","C", "D"],
"B":["E"],
"C":["F","G"],
"D":["H"],
"E":["I"],
"F":["J"]}


path = recursive_dfs(graph, "A")

print(" ".join(path))

Depth First Search on a Binary Tree

What is a Binary Tree?

A binary tree is a special kind of graph in which each node can have only two children or no child.
Another important property of a binary tree is that the value of the left child of the node will be less than or equal to the current node’s value.
Similarly, the value in the right child is greater than the current node’s value.

Representing Binary Trees using Python classes

We can create a class to represent each node in a tree, along with its left and right children.
Using the root node object, we can parse the whole tree.

class Node:

def __init__(self, value):

self.value = value

self.left = None

self.right = None


def insert(self, value):

if value:

if value < self.value:

if self.left is None:

self.left = Node(value)

else:

self.left.insert(value)

elif value > self.value:

if self.right is None:

self.right = Node(value)

else:

self.right.insert(value)

else:

self.value = value
root = Node(7)

root.insert(2)

root.insert(25)

root.insert(9)

root.insert(80)

root.insert(0)

root.insert(5)

root.insert(15)

root.insert(8)

Implementing DFS for a binary tree

Let’s now define a recursive function that takes as input the root node and displays all the values in the tree in the ‘Depth First Search’ order.

def dfs_binary_tree(root):

if root is None:

return

else:

print(root.value,end=" ")

dfs_binary_tree(root.left)

dfs_binary_tree(root.right)
dfs_binary_tree(root)

Depth First Search using networkx

So far, we have been writing our logic for representing graphs and traversing them.
But, like all other important applications, Python offers a library to handle graphs as well. It is called ‘networkx’.

Constructing a graph in networkx

To construct a graph in networkx, we first create a graph object and then add all the nodes in the graph using the ‘add_node()’ method, followed by defining all the edges between the nodes, using the ‘add_edge()’ method.

import networkx as nx

G = nx.Graph() #create a graph

G.add_node(1) # add single node

G.add_node(2)

G.add_node(3)

G.add_node(4)

G.add_node(5)

G.add_nodes_from([6,7,8,9]) #add multiple nodes
# adding edges

G.add_edge(5,8)

G.add_edge(5,4)

G.add_edge(5,7)

G.add_edge(8,2)

G.add_edge(4,3)

G.add_edge(4,1)

G.add_edge(7,6)

G.add_edge(6,9)

Visualizing the graph in DFS

Now, we constructed the graph by defining the nodes and edges let’s see how it looks the networkx’s ‘draw()’ method and verify if it is constructed the way we wanted it to be. We will use matplotlib to show the graph.

import matplotlib.pyplot as plt

nx.draw(G, with_labels=True, font_weight='bold')

plt.show()

Graph traversal in networkx — DFS

The ‘networkx’ offers a range of methods for traversal of the graph in different ways. We will use the ‘dfs_preorder_nodes()’ method to parse the graph in the Depth First Search order.

dfs_output = list(nx.dfs_preorder_nodes(G, source=5))

print(dfs_output)

Topological sorting using Depth First Search

Topological sorting is one of the important applications of graphs used to model many real-life problems where the beginning of a task is dependent on the completion of some other task.

dag = nx.digraph.DiGraph()

dag.add_nodes_from(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'])

dag.add_edges_from([('A', 'B'), ('A', 'E'), ('B', 'D'), ('E', 'C'),
('D', 'G'),('C', 'G'),('C', 'I'), ('F', 'I')])
def dfs(dag, start, visited, stack):

if start in visited:

# node and all its branches have been visited
return stack, visited


if dag.out_degree(start) == 0:

# if leaf node, push and backtrack
stack.append(start)

visited.append(start)

return stack, visited

#traverse all the branches
for node in dag.neighbors(start):

if node in visited:

continue

stack, visited = dfs(dag, node, visited, stack)

#now, push the node if not already visited
if start not in visited:

print("pushing %s"%start)

stack.append(start)

visited.append(start)

return stack, visited

def topological_sort_using_dfs(dag):

visited = []

stack=[]

start_nodes = [i for i in dag.nodes if dag.in_degree(i)==0]

# print(start_nodes)

for s in start_nodes:

stack, visited = dfs(dag, s, visited, stack)

print("Topological sorted:")

while(len(stack)!=0):

print(stack.pop(), end=" ")
topological_sort_using_dfs(dag)
topological_sorting = nx.topological_sort(dag)

for n in topological_sorting:

print(n, end=' ')

Finding connected components using DFS

A graph has another important property called the connected components. A connected component in an undirected graph refers to a set of nodes in which each vertex is connected to every other vertex through a path.

graph = nx.Graph()

graph.add_nodes_from(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'])

graph.add_edges_from([('A', 'B'), ('B', 'E'), ('A', 'E')]) #component 1

graph.add_edges_from([('C', 'D'), ('D', 'H'), ('H', 'F'), ('F', 'C')]) #component 2

graph.add_edge('G','I') #component 3
import matplotlib.pyplot as plt

nx.draw(graph, with_labels=True, font_weight='bold')

plt.show()
def find_connected_components(graph):

visited = []

connected_components = []

for node in graph.nodes:

if node not in visited:

cc = [] #connected component

visited, cc = dfs_traversal(graph, node, visited, cc)

connected_components.append(cc)

return connected_components

def dfs_traversal(graph, start, visited, path):

if start in visited:

return visited, path

visited.append(start)

path.append(start)

for node in graph.neighbors(start):

visited, path = dfs_traversal(graph, node, visited, path)

return visited, path
connected_components = find_connected_components(graph)

print("Total number of connected components =", len(connected_components))

for cc in connected_components:

print(cc)

Conclusion

In this blog, we understood the DFS algorithm and used it in different ways.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store