text: ## 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)}
  
  1. Suppose we are considering adding edges to or removing edges from G.
  1. For the given size of V, what is the maximum possible size of E (assuming no self-loops)?
  2. For the given size of V, what is the minimum possible size of E?
  
  2. 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,
  1. How much space would it take to store G using
  1. an adjacency list?
  2. an adjacency matrix?
  2. 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
  1. |E| = |V|
  2. |E| = |V|2
  
  For questions 3-7, assume that "for each adjacent vertex" in any relevant algorithm takes the vertices in alphabetical order.
  
  3. Show the order in which the vertices will be visited in a breadth-first search from A.
  
  4. Show the order in which the vertices will be visited in a depth-first search from A.
  
  5. Find a topological sort of the vertices using
  1. a post-visit depth-first search.
  2. the queue-based method.
  
  6. Viewing this as an undirected graph, find a minimum spanning tree using
  1. Prim's algorithm
  2. Kruskal's algorithm
  
  7. Use Dijkstra's algorithm to find the shortest route and distance from A to every other vertex.