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 reference 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.
 As we have discussed, a tree is a special case of a graph.
 What edges would you have to remove from the graph above to turn
it into a binary tree with the root at A?
 Draw the resulting tree, arranging the children of each node in
alphabetical (i.e., the label of the left child should be smaller than
the label of the right child). What tree
traversal are you doing if you start at the root and do a
 DFS?
 BFS?
 Use Dijkstra's algorithm to find the shortest route and distance from
A to every other vertex.
 Viewing this as an undirected graph, find a minimum spanning tree
using
 Prim's algorithm
 Kruskal's algorithm