Minimum Spanning Trees (Kruskal's Algorithm) (DP IB Applications & Interpretation (AI)): Revision Note
Did this video help you?
Kruskal's algorithm
How can I use Kruskal’s Algorithm to find a minimum spanning tree?
STEP 1
Sort the edges in terms of increasing weightSTEP 2
Select the edge of least weightIf there is more than one edge of the same weight then either may be used
STEP 3
Look at the edge with the next least weightIf it would form a cycle with your currently selected edges then reject it
Otherwise, select it
STEP 4
Repeat step 3 until all the vertices in the graph are connectedCount the number of edges
If there are n vertices then you stop once you have n-1 edges
Examiner Tips and Tricks
When Kruskal's algorithm, make sure that you state the order in which you consider the edges to get full marks for working! Also, show the edges that you reject.
Worked Example
Consider the weighted graph G below.

a) Use Kruskal’s algorithm to find the minimum spanning tree. Show each step of the algorithm clearly.

b) State the total weight of the minimum spanning tree.

Unlock more, it's free!
Did this page help you?