CPSC 220 Fall 2006
HW 16: Graph Algorithms

Consider the undirected 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. Use Kruskal's algorithm to find a minimum spanning tree. Clearly show the order in which the edges are added to the tree.

2. Starting at A, use Prim's algorithm to find a minimum spanning tree. Clearly show the order in which the edges and vertices are added to the tree.

3. Are your trees in (1) and (2) the same?
   • If yes, will they be the same for every graph? Explain.
   • If no, show that they are both minimum.

4. Viewing this as a directed graph, use the DFS postvisit algorithm we discussed to find a topological sort of the vertices. (Recall that we wrote a method topo that was just like DFS except that it added the current vertex to the result list after making all of the recursive calls instead of before.) In addition to the final sort, show the order in which the recursive calls are made to method topo.