Prim's Algorithm (Edexcel A Level Further Maths: Decision Maths 1)

What is Prim's algorithm?

• Prim's algorithm is another method of finding the minimum spanning tree in a network
• It can be used when the information for a network is given as a graph or in a matrix 

What are the steps in Prim’s Algorithm when using a graph?

• Prim’s algorithm involves adding edges from vertices that are already connected to the tree.
• Cycles are avoided by only adding edges that are not already connected at one end.
   
• STEP 1
  Start at any vertex and choose the edge of least weight that is connected to it
   
• STEP 2
  Choose the edge of least weight that is incident (connected) to any of the vertices already connected and does not connect to another vertex that is already in the tree
  • If there is a choice of the edges of equal weight, either can be selected
     
• STEP 3
  Repeat STEP 2 until all of the vertices are added to the tree

How do you apply Prim’s algorithm to a matrix?

• A minimum spanning tree is built up from the least weight edges that are incident to vertices already in the tree by looking at the relevant rows in the distance matrix
   
• STEP 1
  Select any vertex to start from, cross out the values in the column associated with that vertex and label the row associated with the vertex 1
   
• STEP 2
  Circle the lowest value in any cell along that row and add the edge to your tree, cross out the remaining values in the column of the cell that you have circled
   
• STEP 3
  Label the row associated with the same vertex as the column in the previous STEP with the next number
   
• STEP 4
  Circle the lowest value in any cell along any of the rows that have been labelled and add the edge to your tree, cross out the remaining values in the column of the cell that you have circled
   
• STEP 5
  Repeat STEPS 3 and 4 until all vertices have been added to the tree

• Some versions of Prim's algorithm using a matrix will cross out rows and label columns