خوارزمية BFS

Based on Breadth First Search (BFS) algorithm’s code given in lab, answer the following Questions:

Q1)Add to the code so it prints out the order of nodes (As letters) visited by BFS:Output: A , B , E , F, D, H, G, I, J, C

Q2) make change in the code so it resembles the following graph:

Write change(s) you made, then print out the result:

Q3)based on Graph you built in Q1, change in the code so the BFS start on node with letter (‘B’), then print out the result:

الكود

class Vertex:
def __init__(self, n):
      self.name = n
self.neighbors = list()

self.distance = 9999
self.color = 'black'

def add_neighbor(self, v):
if v not in self.neighbors:
self.neighbors.append(v)
self.neighbors.sort()

class Graph:
   vertices = {}

def add_vertex(self, vertex):
if isinstance(vertex, Vertex) and vertex.name not in self.vertices:
self.vertices[vertex.name] = vertex
return True
      else:
return False

   def add_edge(self, u, v):
if u in self.verticesand v in self.vertices:
for key, value in self.vertices.items():
if key == u:
value.add_neighbor(v)
if key == v:
value.add_neighbor(u)
return True
      else:
return False

   def print_graph(self):
for key in sorted(list(self.vertices.keys())):
         print(key + str(self.vertices[key].neighbors) + "  " + str(self.vertices[key].distance))

def bfs(self, vert):
      q = list()
vert.distance = 0
vert.color = 'red'
for v in vert.neighbors:
self.vertices[v].distance = vert.distance + 1
q.append(v)

while len(q) >0:
         u = q.pop(0)
node_u = self.vertices[u]
node_u.color = 'red'

for v in node_u.neighbors:
node_v = self.vertices[v]
if node_v.color == 'black':
q.append(v)
if node_v.distance>node_u.distance + 1:
node_v.distance = node_u.distance + 1

g = Graph()
a = Vertex('A')
g.add_vertex(a)
g.add_vertex(Vertex('B'))
for iin range(ord('A'), ord('K')):
g.add_vertex(Vertex(chr(i)))

edges = ['AB', 'AE', 'BF', 'CG', 'DE', 'DH', 'EH', 'FG', 'FI', 'FJ', 'GJ', 'HI']
for edge in edges:
g.add_edge(edge[:1], edge[1:])

g.bfs(a)
g.print_graph()