Implement DFS traversal algorithm using python

DFS traversal algorithm
Spread the love

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.

DFS traversal algorithm
DFS traversal algorithm
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
        self.adj_list = {}

        for node in self.nodes:
            self.adj_list[node] = []

    def print_adj_list(self):
        for node in self.nodes:
            print("{} -> {}".format(node, self.adj_list[node]))

    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        if not self.is_directed:
            self.adj_list[v].append(u)

    def add_multiple_edges(self, edges):
        for u, v in edges:
            self.add_edge(u, v)

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.add_multiple_edges(edges)
        self.color = {}
        self.parent = {}
        self.traverse_time = {}
        self.output = []
        self.time = 0

        for node in self.adj_list.keys():
            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
        for v in self.adj_list[source]:
            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.add_multiple_edges(edges)
        self.color = {}
        self.parent = {}
        self.traverse_time = {}
        self.output = []
        self.time = 0

        for node in self.adj_list.keys():
            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
        for v in self.adj_list[source]:
            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']
Read More: Implement BFS algorithm using python OOP

Spread the love

About Anisur Rahman Shahin

Hello. My name is Shahin. I'm a tech enthusiast guy. Personally, I’m an Optimistic and always in hurry kinda person. I'm a freelance web developer. I am working at Zakir Soft as Laravel Developer. My Portfolio website: https://tutspack.com

View all posts by Anisur Rahman Shahin →

Leave a Reply

Your email address will not be published.