Kruskal's algorithm finds a minimum spanning tree (MST) by repeatedly selecting the available edge with the smallest weight, provided that adding it does not create a cycle. For a graph with vertices, it stops when exactly edges have been selected.
A minimum spanning tree connects every vertex in a connected, weighted, undirected graph with the smallest possible total edge weight. It contains no cycles.
| Stage | Action |
|---|---|
| 1 | List all edges in ascending order of weight. |
| 2 | Select the edge with the smallest available weight. |
| 3 | Reject the edge if it would create a cycle; otherwise, include it. |
| 4 | Repeat until the tree contains edges. |
| 5 | Add the selected weights to find the MST's total weight. |
Worked Example
Suppose a graph has vertices A, B, C and D, with weighted edges AB , AC , BC , BD , and CD .
The edges are already ordered. Select AB and AC. Reject BC because A, B and C are already connected, so BC would form a cycle. Select BD, giving the required edges.
The MST is therefore , with total weight
The method works because of the cut property: the lowest-weight edge connecting two currently separate parts of the graph can be included without preventing a minimum solution. Rejecting cycle-forming edges ensures that no unnecessary connection is added.
A common misconception is that Kruskal's algorithm must begin at a chosen vertex. It does not; that is characteristic of Prim's algorithm. Kruskal's considers edges globally from smallest to largest.
Exam Technique
This is AHL 3.16, so it is HL-only content and may appear in a GDC-active Paper 1, Paper 2 or Paper 3 question. Show the selected edge order, clearly mark rejected cycle-forming edges, draw or list the final tree, and state its total weight; a final weight alone is not sufficient evidence of the algorithm.