خوارزمية BFS

Rawan • منذ شهرين

 

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()

كلمات دليلية: bfs

ساعد بالإجابة

"إن في قضاء حوائج الناس لذة لا يَعرفها إلا من جربها، فافعل الخير مهما استصغرته فإنك لا تدري أي حسنة تدخلك الجنة."

لايوجد لديك حساب في عالم البرمجة؟

تحب تنضم لعالم البرمجة؟ وتنشئ عالمك الخاص، تنشر المقالات، الدورات، تشارك المبرمجين وتساعد الآخرين، اشترك الآن بخطوات يسيرة !