CPSC 220
Graph Exercises
SHOW ALL WORK!!!
Consider the directed weighted graph G with vertex and edge sets below:
V = {A,B,C,D,E,F,G}
E = {(A,B,10),
(A,D,20),
(B,C,2),
(B,D,6),
(B,F,6),
(B,G,8),
(C,E,8),
(D,F,5),
(D,G,1)
(G,E,1)
(G,F,3)}
 Suppose we are considering adding edges to or removing edges from G.
 For the given size of V, what is the maximum possible size of E (assuming
no selfloops)?
 For the given size of V, what is the minimum possible size of E?
 Assume that an integer takes one cell and a pointer takes two
cells, and it is not necessary to store the actual label on each vertex,

How much space would it
take to store G using
 an adjacency list?
 an adjacency matrix?
 Develop a general formula in terms of V and E
for the space required for each
representation under these assumptions. Then evaluate the space tradeoffs
when
 E = V
 E = V^{2}
For questions 37, assume that "for each adjacent vertex" in
any relevant algorithm takes
the vertices in alphabetical order.
 Show the order in which the vertices will be visited in a breadthfirst
search from A.
 Show the order in which the vertices will be visited in a depthfirst
search from A.
 Find a topological sort of the vertices using
 a postvisit depthfirst search.
 the queuebased method.
 Viewing this as an undirected graph, find a minimum spanning tree
using
 Prim's algorithm
 Kruskal's algorithm
 Use Dijkstra's algorithm to find the shortest route and distance from
A to every other vertex.