QUESTION 1 Write the adjacency-matrix representation of the graph below. Upload a file with your solution.
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
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