## CPSC 220 Fall 2006

HW 16: Graph Algorithms

**SHOW ALL WORK!!!**
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)}

- Use Kruskal's algorithm to find a minimum spanning tree. Clearly show
the order in which the edges are added to the tree.

- 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.

- 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.

- 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*.