Friday, 18 August 2017

BFS Implementation in Python

Breadth First Search (BFS) algorithm is used to traverse a graph in a breadth ward motion. BFS Algorithm use data structure queue to remember to get the next vertex to start the search and we will required an array to keep the track of vertex that it is visited or unvisited. Implementation of BFS algorithm with example is given below.





In BFS traversal we start the source vertex, display and mark it as visited and look for its adjacent vertices which are unvisited, display them and mark them visited and put them in the queue. If we  not found any adjacent vertex to the source node which is unvisited then, we pop out the first element of queue and do the same thing for the popped element. This steps will be repeated until the queue becomes empty.

PROGRAM:

from collections import defaultdict

class graph:
 def __init__(self):
  self.graph=defaultdict(list)

 def addedge(self,u,v):
  self.graph[u].append(v)
  self.graph[v].append(u)

 def BFS(self,s):
  queue=[]
  visited=[False for i in range(len(self.graph))]
  queue.append(s)
  visited[s]=True
  while queue:
   source=queue.pop(0)
   print(source,end=' ')
   for i in self.graph[source]:
    if visited[i]==False:
     queue.append(i)
     visited[i]=True
     
g=graph()
g.addedge(0, 1)
g.addedge(0, 2)
g.addedge(1, 3)
g.addedge(2, 3)
g.addedge(3, 4)
g.addedge(4, 5)
print("\n\nThe BFS traversal of the above graph is:\n\n")
g.BFS(1)
print("\n\n")



OUTPUT:




EmoticonEmoticon