Depth First Search (DFS) Technique in Python


Depth First Search (DFS) Technique in Python

Depth First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking.
It uses a stack data structure, either explicitly or implicitly through recursion, to keep track of the vertices to be visited next.
DFS can be used to solve various problems such as finding connected components, topological sorting, and detecting cycles in graphs.

Python Implementation of DFS

# Import necessary libraries

from collections import defaultdict

"""
Class to represent a graph using an adjacency list representation.
"""
class Graph:
    def __init__(self):
        """
        Initialize the graph with an empty dictionary to hold adjacency lists.
        """
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        """
        Method to add an edge to the graph.

        Parameters:
        u (int): Source vertex
        v (int): Destination vertex
        """
        self.graph[u].append(v)

    def _dfs_util(self, v, visited):
        """
        Recursive function used by DFS.

        Parameters:
        v (int): The starting vertex
        visited (set): Set to keep track of visited vertices
        """
        # Mark the current node as visited and print it
        visited.add(v)
        print(v, end=' ')

        # Recur for all the vertices adjacent to this vertex
        for neighbour in self.graph[v]:
            if neighbour not in visited:
                self._dfs_util(neighbour, visited)

    def dfs(self, v):
        """
        Method to perform DFS traversal starting from vertex v.

        Parameters:
        v (int): The starting vertex
        """
        # Create a set to store visited vertices
        visited = set()

        # Call the recursive helper function to print DFS traversal
        self._dfs_util(v, visited)

"""
Main method to test the DFS algorithm.
"""
if __name__ == "__main__":
    g = Graph()
    g.add_edge(0, 1)
    g.add_edge(0, 2)
    g.add_edge(1, 2)
    g.add_edge(2, 0)
    g.add_edge(2, 3)
    g.add_edge(3, 3)

    print("Following is Depth First Traversal starting from vertex 2:")
    g.dfs(2)
        

Explanation

The above program demonstrates the Depth First Search (DFS) algorithm in Python:

  • Graph Class: The Graph class represents a graph using an adjacency list representation. It has methods to add edges and perform DFS.
  • _dfs_util Method: This is a recursive method used by the dfs method to visit nodes. It marks the current node as visited, prints it, and then recursively visits all adjacent vertices that have not been visited yet.
  • dfs Method: This method initializes the visited set and calls the _dfs_util method to start the traversal from the given starting vertex.
  • Main Method: This is the entry point of the program where a graph is created, edges are added, and the DFS traversal is initiated starting from vertex 2.

In the main method, we create a graph with 4 vertices and add edges between them. The DFS traversal starts from vertex 2 and prints the nodes in the order they are visited.


By Aditya Bhuyan

I work as a cloud specialist. In addition to being an architect and SRE specialist, I work as a cloud engineer and developer. I have assisted my clients in converting their antiquated programmes into contemporary microservices that operate on various cloud computing platforms such as AWS, GCP, Azure, or VMware Tanzu, as well as orchestration systems such as Docker Swarm or Kubernetes. For over twenty years, I have been employed in the IT sector as a Java developer, J2EE architect, scrum master, and instructor. I write about Cloud Native and Cloud often. Bangalore, India is where my family and I call home. I maintain my physical and mental fitness by doing a lot of yoga and meditation.

Leave a Reply

Your email address will not be published. Required fields are marked *

error

Enjoy this blog? Please spread the word :)