Depth First Traversal (or Search) for a graph is similar to Depth First Traversal of a tree. The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a boolean visited array.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | from collections import defaultdict #This class represents a directed graph #using adjacency list trepresentation 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 DFSuse(self,v,visited): #Mark the current node as visited #and print it visited[v]=True print v, #recur for all vertices adjacent to this vertex for i in self.graph[v]: if visited[i]==False: self.DFSuse(i,visited) #Function for DFS traversal #It uses DFSuse function def DFS(self,v): #Mark all the vertices as not visited visited=[False]*(len(self.graph)) #Now call the recursive DFSuse function to #print DFS traversal self.DFSuse(v,visited) # Main code 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 DFS from (starting from vertex 2)" g.DFS(2) |