COS 226 PROBLEM SET 8

1. Draw the depth-first search forest for the graph defined by the edges 
     AB AC AD AG DE EF FG FI IJ FH
assuming an adjacency-matrix representation.







2. Explain how to modify depth-first search to count the number of cycles in an undirected graph.






3. Consider the following points in the plane: 

     (2, 1) (2, 5) (1, 6) (6, 6) (3, 4) (3, 5) (5, 2) (5, 7)
Label them A through H, respectively. Give the order in which the edges of the Euclidean MST (the MST of the implied complete graph) are discovered by Kruskal's algorithm.




4. Answer the previous question for Prim's algorithm (adjacency matrix representation).




5. Give the all-shortest-paths matrix for the following graph (weights in parentheses): 

     AB(1) AC(2) AD(3) AG(1) DE(4) EF(2) CF(1)







Due: in precept on April 20 or 21.

Do your work on this page (use the back if you must)