1. There are two general approaches for traversing a graph from some starting vertex s: Depth First Search (DFS) where you explore as deeply into the graph as possible. If you reach a “dead end,” webacktrack to the deepest vertex that allows us to try a different path. Breadth First Search (BFS) where you find all vertices a distance 1 (directly connected) from s, before finding allvertices a distance 2 from s, etc.What data structure would be helpful in each type of search? Why?a) Depth First Search (DFS):b) Breadth First Search (BFS): 2. How could you use the bfs algorithm to solve the word ladder problem?3. How would you augment the LinkedVertex and LinkedDirectedGraph classes to keep track of the solution to theword ladder? Data Structures (810:052) Lecture 27 Name:_________________Lecture 27 Page 1Data Structures (810:052) Lecture 27 Name:_________________Lecture 27 Page 2""" File: graph.py """class LinkedEdge(object): def __init__(self, fromVertex, toVertex, \ weight = None): self._vertex1 = fromVertex self._vertex2 = toVertex self._weight = weight self._mark = False def clearMark(self): self._mark = False def __eq__(self, other): if self is other: return True if type(self) != type(other): return False return self._vertex1 == other._vertex1 and \ self._vertex2 == other._vertex2 def getOtherVertex(self, thisVertex): if thisVertex == None or thisVertex == \ self._vertex2: return self._vertex1 else: return self._vertex2 def getToVertex(self): return self._vertex2 def getWeight(self): return self._weight def isMarked(self): return self._mark def setMark(self): self._mark = True def setWeight(self, weight): self._weight = weight def __str__(self): return str(self._vertex1) + ">" + \ str(self._vertex2) + ":" + \ str(self._weight)class LinkedVertex(object): def __init__(self, label): self._label = label self._edgeList = [] self._mark = False def clearMark(self): self._mark = False; def getLabel(self): return self._label def isMarked(self): return self._mark def setLabel(self, label, g): g._vertices.pop(self._label, None) g._vertices[label] = self self._label = label def setMark(self): self._mark = True def __str__(self): return str(self._label)# class LinkedVertex continued # Methods used by LinkedGraph def addEdgeTo(self, toVertex, weight): edge = LinkedEdge(self, toVertex, weight) self._edgeList.append(edge) def getEdgeTo(self, toVertex): edge = LinkedEdge(self, toVertex) try: return self._edgeList[self._edgeList.index(edge)] except: return None def incidentEdges(self): return iter(self._edgeList) def neighboringVertices(self): vertices = [] for edge in self._edgeList: vertices.append(edge.getOtherVertex(self)) return iter(vertices) def removeEdgeTo(self, toVertex): edge = LinkedEdge(self, toVertex) if edge in self._edgeList: self._edgeList.remove(edge) return True else: return Falseclass LinkedDirectedGraph(object): def __init__(self, collection = None): self._vertexCount = 0 self._edgeCount = 0 self._vertices = {} if collection != None: for label in collection: self.addVertex(label) # Methods for clearing, marks, sizes, string rep def clear(self): self._vertexCount = 0 self._edgeCount = 0 self._vertices = {} def clearEdgeMarks(self): for edge in self.edges(): edge.clearMark() def clearVertexMarks(self): for vertex in self.vertices(): vertex.clearMark() def isEmpty(self): return self._vertexCount == 0; def sizeEdges(self): return self._edgeCount def sizeVertices(self): return self._vertexCount def __str__(self): result = str(self.sizeVertices()) + " Vertices: " for vertex in self._vertices: result += " " + str(vertex) result += "\n"; result += str(self.sizeEdges()) + " Edges: " for edge in self.edges(): result += " " + str(edge) return resultThe case study in section 20.9, discusses a menu-drivengraph-testing program which uses theLinkedDirectedGraph class. The graph is input byspecifying the directed edges as strings of the form: "p>q:0", where p and q are vertice labels with a directededge from p to q with a weight of 0. Vertices are inferredfrom the edges, except for disconnected vertices that arestrings of just vertex labels. Consider the graph formaking pancakes. Vertices are ingredients or steps, andedges represents the partial order among the steps.3/4 cup milk1 egg1 Tbl oil1 cup flour mix the batterpour 1/2 cupheat griddleturn when bubblyeatheat syrup of batterThe file pancakes.txt has two lines, where the first describes the edges and the second containing a start vertex milk>mix:0 egg>mix:0 oil>mix:0 flour>mix:0 mix>syrup:0 mix>pour:0 heat>pour:0 syrup>eat:0 pour>turn:0 turn>eat:0milkA topological sort algorithm (in the algorithms.py module) can use a recursive dfs to determine a proper order toavoid putting the "cart before the horse." For example, we don't want to "pour ½ cup of batter" before we "mix thebatter", and we don't want to "mix the batter" until all the ingredients have been added. I've modified thealgorithms.py module to include some additional print statements in the topoSort and dfs functions. Data Structures (810:052) Lecture 27 Name:_________________Lecture 27 Page 3# class LinkedDirectedGraph continued # Vertex related methods def addVertex(self, label): self._vertices[label] = LinkedVertex(label) self._vertexCount += 1 def containsVertex (self, label): return label in self._vertices def getVertex(self, label): return self._vertices[label] def removeVertex(self, label): removedVertex = self._vertices.pop(label, None) if removedVertex is None: return False # Examine all vertices for vertex in self.vertices(): if vertex.removeEdgeTo(removedVertex):