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.
 
 
 
 
 
 

64 lines
1.5 KiB

  1. # Python3 Program to print BFS traversal
  2. from collections import defaultdict
  3. # This class represents a directed graph
  4. # using adjacency list representation
  5. class Graph:
  6. # Constructor
  7. def __init__(self):
  8. # default dictionary to store graph
  9. self.graph = defaultdict(list)
  10. # function to add an edge to graph
  11. def addEdge(self,u,v):
  12. self.graph[u].append(v)
  13. # Function to print a BFS of graph
  14. def BFS(self, s):
  15. # Mark all the vertices as not visited
  16. visited = [False] * (len(self.graph))
  17. # Create a queue for BFS
  18. queue = []
  19. # Mark the source node as
  20. # visited and enqueue it
  21. queue.append(s)
  22. visited[s] = True
  23. while queue:
  24. # Dequeue a vertex from
  25. # queue and print it
  26. s = queue.pop(0)
  27. print (s, end = " ")
  28. # Get all adjacent vertices of the
  29. # dequeued vertex s. If a adjacent
  30. # has not been visited, then mark it
  31. # visited and enqueue it
  32. for i in self.graph[s]:
  33. if visited[i] == False:
  34. queue.append(i)
  35. visited[i] = True
  36. # Driver code
  37. g = Graph()
  38. g.addEdge(0, 1)
  39. g.addEdge(0, 2)
  40. g.addEdge(1, 2)
  41. g.addEdge(2, 0)
  42. g.addEdge(2, 3)
  43. g.addEdge(3, 3)
  44. print ("Following is Breadth First Traversal"
  45. " (starting from vertex 2)")
  46. g.BFS(2)