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
 

1. Select the shortest edge in a network
2. Select the next shortest edge which does not create a cycle
3. Repeat step 2 until all vertices have been connected

 
Prim’s Algorithm
 

1. Select any vertex
2. Select the shortest edge connected to that vertex
3. Select the shortest edge connected to any vertex already connected
4. 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
 

1. Select a vertex
   > circle the letter at the top – label it 1
   > cross out the row corresponding to the vertex
   
   
2. Select the smallest number in labelled column(s)
   
   
3. Cross out the row, label the column corresponding to crossed-out row
   
   
4. Repeat steps 2 and 3 until all columns are labelled
   
   
5. List the edges which have been selected
   
   
6. Draw the MST
   
   

Example:
 
This is our distance matrix, in table form.                                                                

Step 1

Step 2 and 3

Step 4

Step 5

Step 6