NAME:

PRECEPT:

COS 226 Exercises on MST


1. Label the following points in the plane A through I, respectively: 
(1, 3) (2, 1) (2, 6) (1, 6) (6, 6) (3, 4) (3, 6) (5, 2) (5, 7)
Taking edge lengths to be weights, consider the weighted graph defined by the edges 
A-B A-C C-G F-G B-F B-E B-H B-D D-H E-I G-I E-F E-H
Give the order in which the edges of the MST are discovered by Kruskal's algorithm, breaking any ties in favor of the lexicographically smallest edge (e.g., edge A-C is chosen before B-F which is chosen before B-H).

Hint: to simplify your calculations, you can use the squares of the distances instead of the distances. Most MST algorithms (including Kruskal and Prim) only compares edge weights. Using the squares of the distances will produce exactly the the same answers to every comparison.

















2. Answer question 1 for Prim's algorithm (adjacency matrix representation) starting the search at A.