# 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 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 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))`

# 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 nxG = nx.Graph() #create a graphG.add_node(1) # add single nodeG.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 edgesG.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 pltnx.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 1graph.add_edges_from([('C', 'D'), ('D', 'H'), ('H', 'F'), ('F', 'C')]) #component 2graph.add_edge('G','I') #component 3`
`import matplotlib.pyplot as pltnx.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.