Bredth-first search algorithm is used for transversing or searching tree or group data structures.It starts at the tree root and explores all of the neighbor nodes at the present depth prior to moving on the nodes to the next level.
from collections import defaultdict
#list representation
class Graph:
#constructor
def __init__(self):
self.graph=defaultdict(list)
#function to add an edge to graph
def addEdge(self,u,v):
self.graph[u].append(v)
#function to print BFS graph
def BFS(self,s):
#mark all the vertices as not visited
visited=[False]*(len(self.graph))
print(visited)
#created a queue for BFS
queue=[]
queue.append(s) #mark the source node as visited and enqueue it
print("the append S is",s)
visited[s]=True
print(visited)
while queue:
#dequeue a vertex from queue and print it
s=queue.pop(0)
print(s)
#get all adjacend vertices of the dequed
#vertex s,if a adjacement has not been visited
#then mark it as visited and enque it
for i in self.graph[s]:
if visited[i]==False:
queue.append(i)
visited[i]=True
print("second visit",visited)
#driver code
#create a graph given in the above diagram
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)
g.BFS(2)
