Python Code 

class Graph:

def __init__(self, graph_repr=None):
if graph_repr is None:
self.vertList = {}
else:self.vertList = graph_repr

def addVertex(self,key):
if key not in self.vertList:
self.vertList[key] = []
return self.vertList

def addEdge(self,frm,to,cost=1):
if frm not in self.vertList:
self.addVertex(frm)
if to not in self.vertList:
self.addVertex(to)
self.vertList[frm].append((to, cost))
return self.vertList

def bfs(self, start):
# Your code starts here

def dfs(self, start):
# Your code starts here

### EXTRA CREDIT, uncomment method definition if submitting extra credit

#def dijkstra(self,start):
# Your code starts here

In Module 6, we discussed the Graph data structure. Since the graph is a non-linear structure, there is no unique traversal. Nodes can be found using Breadth-First Search (visit the sibling nodes before visiting the child nodes) and Depth-first search (visit the child nodes before visiting the sibling nodes). Based on the implementation of the Graph data structure discussed during our lecture (provided in the starter code): 1. Create the method bfs(start). This method takes the key of the starting node and performs Breadth-first search in an instance of the class Graph. This method must return a list that contains the order in which the nodes where accessed during the search (following alphabetical order when discovering nodes). You must use your queue code from LAB 10 in order to produce your result. If you don't use the queue, your will not receive credit for the assignment 2. Create the method dfs(start). This method takes the key of the starting node and performs Depth-first search in an instance of the class Graph. This method must return a list that contains the order in which the nodes where accessed during the search (following alphabetical order when discovering nodes). You must use your stack code from LAB 9 in order to produce your result. If you don't use the stack, your will not receive credit for the assignment Grading Notes: A random instance of the Graph class (directed or undirected, weighted or unweighted) will be created and the bfs and dfs methods will be called on 4 different starting nodes for 12.5 pts each. Make sure you use the Graph data structure provided in the starter code, otherwise, no credit will be given. Vertices and edges will be provided in random order (non-alphabetical order). The final result should be only the one provided by following alphabetical order.