Python Program for Depth First Search or DFS for a Graph
Depth First Traversal (or DFS) for a graph is similar to Depth First Traversal of a tree. The only catch here is, that, unlike trees, graphs may contain cycles (a node may be visited twice). To avoid processing a node more than once, use a boolean visited array. A graph can have more than one DFS traversal.
Example:
Input: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Output: DFS from vertex 1 : 1 2 0 3Input: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Output: DFS from vertex 2 : 2 0 1 3
How does DFS work?
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.
Below is the implementation of the above approach:
Python3
# Python3 program to print DFS traversal # from a given graph from collections import defaultdict # This class represents a directed graph using # adjacency list representation class Graph: # Constructor def __init__( self ): # Default dictionary to store graph self .graph = defaultdict( list ) # Function to add an edge to graph def addEdge( self , u, v): self .graph[u].append(v) # A function used by DFS def DFSUtil( self , v, visited): # 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 .DFSUtil(neighbour, visited) # The function to do DFS traversal. It uses # recursive DFSUtil() def DFS( self , v): # Create a set to store visited vertices visited = set () # Call the recursive helper function # to print DFS traversal self .DFSUtil(v, visited) # Driver's code if __name__ = = "__main__" : g = Graph() g.addEdge( 0 , 1 ) g.addEdge( 0 , 2 ) g.addEdge( 1 , 2 ) g.addEdge( 2 , 0 ) g.addEdge( 2 , 3 ) g.addEdge( 3 , 3 ) print ( "Following is Depth First Traversal (starting from vertex 2)" ) # Function call g.DFS( 2 ) # This code is contributed by Neelam Yadav |
Following is Depth First Traversal (starting from vertex 2): 2 0 1 3
Time Complexity: O(V+E) where V is the number of vertices in the graph and E is the number of edges
Auxiliary Space: O(V+E)
Please refer complete article on Depth First Search or DFS for a Graph for more details!