I’m completing the datastructures and algorithms preparatory course for a masters in data science.

Here, is a breadth-first search algorithm for a graph I wrote based on the pseudocode provided in the course. I’ve only been using python for a two months or so, so I’m not yet proficient. I also do not have a comp sci background.

Questions: I’ll be super grateful for any response I can get.

I use an id attribute to identify each vertex instance. Instead, is it possible to pass the id in the data attribute as maybe a key:value pair. This is assuming that the data is a dictionary containing different information on the vertex.
If I pass the adj_list list as an argument when creating a Vertex instance, the print_shortestpath() method doesn’t work. I’m not sure why this is. It only works when I set the adj_list after all the involved vertexes in the list have been defined.
For those with experience, Is this how BFS is used in the industry or could you kindly help with feedback on how I can make my implementation or coding better? I seem to have a firm grasp on the concept, but I’m not sure if my implementation is standard or efficient. For example, the pseudocode passes the entire Graph and the source as arguments in the BFS call. I simply call it from the source vertex object. Kindly advise.

Here is the full python code:

from queue import Queue

class Vertex:

“””

Attributes:

d: distance. This variable is relative, depending on the source and destination vertexes in a breadth-first or depth-first search

color: vertex color

p: parent vertex

key: key

data: satellite data added to the vertex datastructure

adj_list: the adjacency list containing the edges to which this vertex is connected

id: a str name to identify the vertex

“””

def init(self, parent = None, id = None, key = None, data = None, adj_list = []):

self.d = float("inf")

self.color = "white"

self.p = parent

self.key = key

self.data = data

self.adj_list = adj_list

self.id = id

def BFS(self):

#initializing the attributes of the source vertex

self.d = 0

self.color = "gray"

#creating a queue for enqueing and dequeing the discovered vertexes

Q = Queue()

Q.put_nowait(self)

while not Q.empty():

  u = Q.get_nowait()

  for v in u.adj_list:

    if v.color == "white":

      v.d = u.d + 1

      #setting the parent here also helps with finding the shortest path between vertices.

      v.p = u

      v.color = "gray"

      #enqueing the discovered vertex after changing its color to gray.

      Q.put_nowait(v)

  u.color = "black"

def print_shortestpath(self, destination_vertex, bfs = False):

"""



Args:

  bfs: Breadth-first search is needed. This boolean variable tells

  the function whether to run BFS (if it has already been run) or not.



Returns:



"""

#conduct a BFS first to map out the different paths from the source to all vertices



# since recursion is used, this conditional statment makes sure BFS() is called

#only once for efficiency.



if bfs == False:

  self.BFS()

else:

  pass



if self == destination_vertex:

  #we have gotten to the source from the destination

  #return

  print(self.id)

  return self

elif destination_vertex.p == None:

  print("No path from the source to the destination vertex exists")

else:

  #recursive call to the parent of the destination vertex with bfs set to True

  self.print_shortestpath(destination_vertex.p, bfs = True)



print(destination_vertex.id)

#testing it out

if name == “main“:

#creating the vertexes

n1 = Vertex(id=”n1″)

n2 = Vertex(id=”n2″)

n3 = Vertex(id=”n3″)

n4 = Vertex(id=”n4″)

n5 = Vertex(id=”n5″)

n6 = Vertex(id=”n6″)

n7 = Vertex(id=”n7″)

n8 = Vertex(id=”n8″)

n9 = Vertex(id=”n9″)

n10 = Vertex(id=”n10″)

#creating the adjacency_list representations of the graph

#connectin vertices to edges

n1.adj_list = [n2, n3, n4]

n2.adj_list = [n1, n5, n9]

n3.adj_list = [n5, n7, n1]

n4.adj_list = [n9, n7]

n5.adj_list = [n2, n3, n6, n8]

n6.adj_list = [n5, n7, n8]

n7.adj_list = [n3, n6, n4]

n8.adj_list = [n5, n6]

n9.adj_list = [n2, n4, n10]

n1.print_shortestpath(n10)

I pass the adj_list list as an argument when creating a Vertex instance.