Problem 1: Graph Practice (10 points) Consider the directed…
Problem 1: Graph Practice (10 points) Consider the directed graph shown below and answer the following questions. (a) Write down the adjacency list representation of the graph, where a dictionary maps each vertex v to its adjacency list Adj, which contains v’s outgoing neighbors listed in alphabetical order. (2 points) (b) Run both BFS and DFS on the graph, starting from node A. While performing each search, visit the outgoing neighbors of a vertex in alphabetical order. For each search, list vertices in the order in which they were first visited. (4 points) (c) It is possible to remove a single edge from the graph to make it a DAG. State every edge with this property, and for each, state a topological sort order of the resulting DAG. (4 points) Congratulations, you are almost done with this quiz. DO NOT end the Honorlock session until you have submitted your work to Gradescope. When you have answered all questions: Use your smartphone to scan your answer sheet and save the scan as a PDF. Make sure your scan is clear and legible. Submit your PDF to Gradescope as follows: Email your PDF to yourself or save it to the cloud (Google Drive, etc.). Click this link to go to Gradescope to submit your work: Quiz 10 Return to this window and click the button below to agree to the honor statement. Click Submit Quiz to end the exam. End the Honorlock session.