What to turn in: Save your answers in a .pdf file and name your file as yourname_HW8.pdf. Upload it under Homework 8 submission link. Q1.Assume that a graph is represented in matrix no

CPS 500 Data Structures and Algorithms HW8 What to turn in: Save your answers in a .pdf file and name your file as yourname_HW8.pdf. Upload it under Homework 8 submission link. Q1. Assume that a graph is represented in matrix notation as follows: A B C D E F A 8 14 8 8 7 9 B 14 8 9 8 8 2 C 8 9 8 6 8 8 D 8 8 6 8 15 11 E 7 8 8 15 8 10 F 9 2 8 11 10 8 a) Represent this graph as an adjacency list. b) Give a DFS traversal of the graph starting at node A. c) Give a BFS traversal of the graph starting at node A. d) Find a minimum spanning tree on this graph. 1e) Apply Dijkstra’s algorithm on this graph to find the shortest path from node A to all other nodes. Draw the graph by clearly indicating the current shortest distances from A to all other nodes at each iteration of the algorithm. Iteration 1 Iteration 2 Iteration 3 Iteration 4 Iteration 5 Iteration 6 2Q2. Assume that you have the following node structure for a graph node: struct Node { char name; // the name of the node int distance; // distance to the starting node struct Node* previous; // previous node on the shortest path } Suppose you have executed Dijsktra’s algorithm on a connected graph and computed the shortest path from a starting node to all other nodes. This algorithm updates the distance and previous fields of all nodes (the previous field of the starting node is set to NULL). The name field was already updated at the beginning of the program. Now you are asked to implement the function below to print the path from the starting node to a given target node “V”. The output must contain the names of the starting node, target node, and all other nodes on the path. You can use any data structure that we learned in this class. You can use cout to print the name of a node. (You can write the function recursively or…