can you explain me the code i ammentioning

0 votes
asked Jul 6, 2018 by anam siddiqui
#Practical 1 : BFS
class Vertex:
    def __init__(self,n):
        self.name=n
        self.neighbors=list()

        self.distance=9999
        self.color='blue'
    def add_neighbors(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.vertices and v in self.vertices:
            for key,value in self.vertices.items():
                if key==u:
                    value.add_neighbors(v)
                if key==v:
                    value.add_neighbors(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 i in range(ord('A'),ord('K')):
  g.add_vertex(Vertex(chr(i)))
  
edges=['AB','AE','BF','CG','DE','EH','FG','FI','FJ','GF','GJ','HI','HE']

for edge in edges:
  g.add_edge(edge[:1],edge[1:])
                          
g.bfs(a)
g.print_graph()

Your answer

Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.
Anti-spam verification:
To avoid this verification in future, please log in or register.
Welcome to OnlineGDB Q&A, where you can ask questions related to programming and OnlineGDB IDE and and receive answers from other members of the community.
...