Minimum Spanning Trees (MSTs)
A spanning tree where the total weight of the arcs is at its minimum.
Minimum Connector Algorithms (MCA):
Kruskal’s Algorithm
Prim’s Algorithm
Remember to write down the order in which you have selected edges to show the examiner which algorithm you have used, especially if they ask for you to use a specific algorithm.
Differences between the MCA’s
Prim’s from a distance matrix
This is our distance matrix, in table form.
Minimum Connector Algorithms (MCA):
Kruskal’s Algorithm
 Select the shortest edge in a network
 Select the next shortest edge which does not create a cycle
 Repeat step 2 until all vertices have been connected
Prim’s Algorithm
 Select any vertex
 Select the shortest edge connected to that vertex
 Select the shortest edge connected to any vertex already connected
 Repeat step 3 until all vertices have been connected
Remember to write down the order in which you have selected edges to show the examiner which algorithm you have used, especially if they ask for you to use a specific algorithm.
Differences between the MCA’s
 Kruskal’s algorithm always begins at the arc of lowest weight while Prim’s can start at any vertex.
 Kruskal’s algorithm forms a MST in a random manner while Prim’s MST ‘grows’ with linking arcs.
 Unlike Kruskal’s algorithm, you do not have to check for cycles with Prim’s algorithm.
 Prim’s algorithm can be applied to a distance matrix while Kruskal’s algorithm cannot.
Prim’s from a distance matrix
 Select a vertex
> circle the letter at the top – label it 1
> cross out the row corresponding to the vertex  Select the smallest number in labelled column(s)
 Cross out the row, label the column corresponding to crossedout row
 Repeat steps 2 and 3 until all columns are labelled
 List the edges which have been selected
 Draw the MST
This is our distance matrix, in table form.

