QUESTION 2

1. Represent the following graph using an Adjacency List.

There are three ways to store graphs - edge lists, adjacency matrices, and adjacency lists. For a directed graph like the one shown below, how much time would it take to search for a particular edge through each way of storing the graph?

Assuming E is the number of edges, V is the number of vertices, and d is the degree of each vertex, categorize the time for edge lists, adjacency matrices, and adjacency lists using O(E), O(1), O(d)

There are two common algorithms for traversing graphs. Name them both and explain their differences.

A minimum spanning tree is a subset of the edges of a graph that connects all the vertices with the minimum sum of edge weights and consists of no cycles. Redraw the graph below clearly showing the minimum spanning tree.

8 2 7 3 6 5 1 2 3 4 5 6 88 7 2 5 8 4 2 9 14 1 11 4 4 9 7 6 8 10 3 6 7 1 2