Repository where I mostly put random python scripts.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 
 
 
 

59 lines
1.3 KiB

  1. # Python3 program to print DFS traversal
  2. from collections import defaultdict
  3. # This class represents a directed graph using
  4. # adjacency list representation
  5. class Graph:
  6. # Constructor
  7. def __init__(self):
  8. # default dictionary to store graph
  9. self.graph = defaultdict(list)
  10. def addEdge(self, u, v):
  11. self.graph[u].append(v)
  12. # A function used by DFS
  13. def DFSUtil(self, v, visited):
  14. # Mark the current node as visited
  15. # and print it
  16. visited[v] = True
  17. print(v, end = ' ')
  18. # Recur for all the vertices
  19. # adjacent to this vertex
  20. for i in self.graph[v]:
  21. if visited[i] == False:
  22. self.DFSUtil(i, visited)
  23. # The function to do DFS traversal. It uses
  24. # recursive DFSUtil()
  25. def DFS(self, v):
  26. # Mark all the vertices as not visited
  27. visited = [False] * (len(self.graph))
  28. # Call the recursive helper function
  29. # to print DFS traversal
  30. self.DFSUtil(v, visited)
  31. # Driver code
  32. # Create a graph given
  33. # in the above diagram
  34. g = Graph()
  35. g.addEdge(0, 1)
  36. g.addEdge(0, 2)
  37. g.addEdge(1, 2)
  38. g.addEdge(2, 0)
  39. g.addEdge(2, 3)
  40. g.addEdge(3, 3)
  41. print("Following is DFS from (starting from vertex 2)")
  42. g.DFS(2)