Prim's Minimum Spanning Tree (mathematician Vojtch Jarnik discovered algorithm a generation earlier) High level algorithm: Pick a vertex to go into a discovered set of vertices While there are vertices that are undiscovered Find the cheapest available edge that discovers a new vertex Place that vertex into the discovered set Place that edge into the minimum spanning tree (When all the vertices have been discovered, a minimum spanning tree is comp The algorithm can be accomplished easily with a sorted list of edges Example 1-Start at vertex E leted.) Sorted T1 T2 T3 T4TS T6 Edges | Tree: Eo, F1, c2, G3Bu Ds, A6 1BG 1CF 2EF Add Add Add | // 1 //1 ADD ! // | 3CD 6DE 7AB 8AD 9BC Add Minimum Spanning Tree: 3CD, 1CF, 2EF, 2FG, 1BG, 7AB Sum: 16