Instructions:

- The work in this assignment must be completed alone.
- Use the starter code provided on this CANVAS assignment. Do not change the function names.
- A doctest is provided as an example of code functionality. Getting the same result as the doctest does not guarantee full credit. You are responsible for debugging and testing your code with enough data, you can share ideas and testing code during your recitation class.
- Each function must return the output (Do not use print in your final submission, otherwise your submissions will receive a -10 point deduction)
- Do not include test code outside any function in the upload. Printing unwanted or illformatted data to output will cause the test cases to fail. Remove all your testing code before uploading your file (You can also remove the doctest). Do not include the input() function in your submission.
- When any function returns an error, it must be a string containing “error”

Goal:

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 11 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 10 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.
EXAMPLE:
Note that this is only an example, the fact that you code produces the example’s output does not ensure your code works properly. Test your code with several examples!

g1 = {'A': ['B','D','G'],
'B': ['A','E','F'],
'C': ['F'],
'D': ['A','F'],
'E': ['B','G'],
'F': ['B','C','D'],
'G': ['A','E']}
>>> g=Graph(g1)
>>> g.bfs('A')
['A', 'B', 'D', 'G', 'E', 'F', 'C']
>>> g.dfs('A')

['A', 'B', 'E', 'G', 'F', 'C', 'D']

g2 = {'F': ['D','C','B'],
'A': ['G','D','B'],
'B': ['F','A','E'],
'E': ['G','B'],
'C': ['F'],
'D': ['F','A'],
'G': ['A','E']}
>>> g=Graph(g2)
>>> g.bfs('A')
['A', 'B', 'D', 'G', 'E', 'F', 'C']
>>> g.dfs('A')
['A', 'B', 'E', 'G', 'F', 'C', 'D']

g3 = {'B': [('E',3),('C',5)],
'F': [],
'C': [('F',2)],
'A': [('D',3),('B',2),],
'D': [('C',1)],
'E': [('F',4)]}
>>> g=Graph(g3)
>>> g.bfs('A')
['A', 'B', 'D', 'C', 'E', 'F']
>>> g.dfs('A')
['A', 'B', 'C', 'F', 'E', 'D']

Using the Stack and Queue for graph traversals

 

BFS 



EXTRA CREDIT: 50 pts, added regardless of the maximum 100 (no partial credit for incorrect answers)

Create the method dijkstra(start). This method takes the key of the starting node and runs Dijkstra's algorithm in an instance of the class Graph. The method returns a dictionary with the value of the shortest path from the starting node to every other node reachable from start.
g3 = {'B': [('E',3),('C',5)],
'F': [],
'C': [('F',2)],
'A': [('D',3),('B',2),],
'D': [('C',1)],
'E': [('F',4)]}
>>> g=Graph(g3)
>>> g.dijkstra('A')
{'A': 0, 'B': 2, 'C': 4, 'D': 3, 'E': 5, 'F': 6}
 

Note: For this method, the dictionary does not have to be in alphabetical order, as long as the pair key, value is correct! i.e. {'A': 0, 'D': 3, 'B': 2, 'C': 4, 'E': 5, 'F': 6}, {'A': 0, 'B': 2, 'D': 3, 'C': 4, 'E': 5, 'F': 6}, etc., are also correct 

Deliverables:

Include all your code (including the stack and queue code) in your script named HW6.py. Submit it to the HW6 Gradescope assignment before the due date