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

2018-03-05
Networking