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.