# Implement DFS traversal algorithm using python

DFS (Depth-First Search) is the graph traversal algorithm. DFS is a recursive algorithm. In this tutorial, I am going to show you how to implement a DFS traversal algorithm using python. To do that, first, you have to know how to input graphs in python on an adjacent list.

#### Algorithm of BFS

Create a recursive function that takes the index of the node and a visited array.

Mark the current node as visited and print the node.
Traverse all the adjacent and unmarked nodes and call the recursive function with the index of the adjacent node.

#### Approch

Depth-first search is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. So the basic idea is to start from the root or any arbitrary node and mark the node and move to the adjacent unmarked node and continue this loop until there is no unmarked adjacent node. Then backtrack and check for other unmarked nodes and traverse them. Finally, print the nodes in the path.

In this tutorial, I will apply DFS to this graph which is a directed graph.

###### Prerequisite : Graph representation in python on Adjacency list

Well, I assumed that you are familiar with how to input graphs in an adjacency list using python. Follow this code of graph. I will not explain to you these pieces of code because already I explain them in my blog.

### Input Graph using adjacency list

``````class Graph:
def __init__(self, nodes, is_directed=False):
self.is_directed = is_directed
self.nodes = nodes

for node in self.nodes:

for node in self.nodes:

if not self.is_directed:

for u, v in edges:

Well, in this graph we can see the six vertices or nodes and five edges. First, you have to make two lists and store the nodes and edges.

``````nodes = ["A", "B", "C", "D", "E", "F"]
edges = [
("A", "B"),
("B", "D"),
("D", "C"),
("D", "E"),
("C", "F"),
]``````

Well, now define a new class whose name is DFS which extends the Graph class that I defined before. Let’s see the code I will explain you later.

``````class DFS(Graph):
def __init__(self, nodes, edges, is_directed=False):
super().__init__(nodes, is_directed)
self.color = {}
self.parent = {}
self.traverse_time = {}
self.output = []
self.time = 0

self.color[node] = "W"
self.parent[node] = None
self.traverse_time[node] = [-1, -1]``````

Well, inside this class you can see a constructor or init method. This init method takes two parameters that are nodes and edges. This init method is also called the super method that means it sends data in the superclass. Well, after I call a method which defined in the base class. This method generates an adjacency list for this graph. After then take a couple of lists and dictionaries

Well, after then execute a loop to do the initial task. Inside the loop, I assign the color of all nodes are white, the parent node of all nodes is equal to None. And finally, the traversal time of all nodes is equal to -1,-1.

### DFS traversal Algorithm

Let’s see the code of the DFS algorithm.

``````def dfs_traversal(self, source):
self.color[source] = "G"
self.traverse_time[source][0] = self.time
self.output.append(source)
self.time += 1
if self.color[v] == "W":
self.parent[v] = source
self.dfs_traversal(v)
self.color[source] = "B"
self.traverse_time[source][1] = self.time
self.time += 1
return self.output``````

Well, In this function you have to send a parameter that is the source node. Well, after then you have to change the color of the source node from white to gray. Then source node’s traversal start time is equal to time after increasing the time value. After then you have to push the source node into the output list.

Well, then you have to execute a loop in the current node’s neighbors. Inside the loop, first, you have to check the neighbor already visited or not. If not visited then assign the parent value of the neighbor node. Then recursively call again the dfs function with the parameter an unvisited neighbor. Well, after the loop changes the color of sources from gray to black as well assign traversal ending time. Then increase time value and return output list.

Well, now create an object then check all functions.

``````dfs = DFS(nodes, is_directed=True, edges=edges)
print(dfs.dfs_traversal("A"))``````

### Full code of DFS Traversal

``````
class DFS(Graph):
def __init__(self, nodes, edges, is_directed=False):
super().__init__(nodes, is_directed)
self.color = {}
self.parent = {}
self.traverse_time = {}
self.output = []
self.time = 0

self.color[node] = "W"
self.parent[node] = None
self.traverse_time[node] = [-1, -1]

def dfs_traversal(self, source):
self.color[source] = "G"
self.traverse_time[source][0] = self.time
self.output.append(source)
self.time += 1
if self.color[v] == "W":
self.parent[v] = source
self.dfs_traversal(v)
self.color[source] = "B"
self.traverse_time[source][1] = self.time
self.time += 1
return self.output

def traversal_of_a_node(self, node):
return self.traverse_time[node]

def print_path(self, destination):
path = []

while destination is not None:
path.append(destination)
destination = self.parent[destination]

path.reverse()

return path

nodes = ["A", "B", "C", "D", "E", "F"]

edges = [
("A", "B"),
("B", "D"),
("D", "C"),
("D", "E"),
("C", "F"),
]
dfs = DFS(nodes, is_directed=True, edges=edges)

print(dfs.dfs_traversal("A"))

// Output
['A', 'B', 'D', 'C', 'F', 'E']
``````