QUESTION 1 Write the adjacency-matrix representation of the graph below. Upload a file with your solution. Attach File QUESTION 2 Let G = (V, E) be a directed, weighted graph which has |V| = 1000 and |E| = 100. Which data structure should be used to represent the graph G? • we cannot represent such a graph G • Binary Search Tree representation • adjacency-matrix graph representation • adjacency-list graph representation QUESTION 3The transpose of a direct graph G = (V, E) is the graph GT = (V, ET) where Thus GT is G with all the edges reversed. Write the pseudocode of an algorithm that computes GT from G using adjacency-matrix graph representation. What is the running time? Upload a file with your solution. Attach File QUESTION 4 Show how breadth-first search (BFS) works on the graph below, where vertex a is the source. o (7 pts) Show the d and π values that result from running BFS. o (1 pt) Show the elements in the queue Q, similar with the examples run in class. o (2 pts) Show the breadth-first tree obtained after running BFS algorithm. Follow the example in the notes. Upload a file with your solution. QUESTION 5 Consider the graph G below. Apply DFS to the graph G. Assume that the vertices are listed in alphabetical order in each adjacency list. In addition, consider that the vertices are taken in the alphabetical orderin the main loop of the DFS algorithm. • (6 pts) Write discovery/finish times for each vertex • (2 pts) Write the edge classification. • (2 pts) Write the depth first forest obtained. Follow the example from the notes. Upload a file with your solution. QUESTION 6 Which of the following lists are possible topological sorts of the graph G below? • a, b, d, c, e, f • a, c, e, f, b, d • b, a, c, d, f, e • a, c, b, d, e, f • e, a, c, b, d, f • c, a, b, d, e, f QUESTION 7 Run Prim (starting from vertex a) and Kruskal algorithms on the graph below: • (5 pts) For Prim's algorithm draw a table that shows the vertices in the queue at each iteration, similar to the example run in class. • (2 pts) Prim's algorithm: using the table from the first part, list the order in which edges are added to the tree. • (3 pts) Kruskal's algorithm: list the order in which edges are added to the tree. QUESTION 8 Consider the graph G below. Which of the following show correct orders of adding edges to the MST using Kruskal's algorithm? • (e,b),(e,f),(a,c),(c,d),(d,e) • (f,e),(b,e),(a,c),(c,d),(a,b) • (e,b),(e,f),(a,c),(c,d),(a,b) • (b,e),(a,c),(c,d),(a,b),(a,f) • (b,e),(a,c),(f,e),(c,d),(d,e) • (b,e),(e,f),(c,a),(a,b),(e,d)