Minimum spanning trees by Prim's and Kruskal's algorithms

Minimum spanning trees

A minimum spanning tree reaches every vertex with no cycle and the least possible total weight. Prim's algorithm grows from a starting vertex, while Kruskal's algorithm considers all edges from lightest to heaviest

1. Use n minus 1 edges A spanning tree on n vertices has exactly n − 1 edges \(\displaystyle |E(T)|=n-1\)
2. Grow from the current tree Prim's algorithm selects a lightest edge with one endpoint in the current tree and the other outside it. A detached edge is not eligible
3. Reject cycle-closing edges Kruskal's algorithm considers edges from lightest to heaviest. Accept an edge only when its endpoints are in different components of the selected edges \(\displaystyle AB,BC\text{ selected};\quad AC\text{ would close a cycle}\)
4. Add the selected weights After finding a minimum spanning tree, add all its selected edge weights \(\displaystyle W(T)=\sum_{e\in T}w(e)\)

Worked example

A network has vertices A, B, C, D and E with edge weights AB = 2, BC = 3, AC = 4, CD = 5, DE = 6, BD = 7 and CE = 8. Use Kruskal's algorithm to find the minimum spanning-tree total

1. \(\displaystyle 2<3<4<5<6<7<8\)Kruskal's algorithm considers the edge weights from smallest to largest
2. \(\displaystyle AB,\;BC\text{ accepted};\quad AC\text{ rejected}\)AB and BC join separate components, but AC would close the cycle A-B-C-A
3. \(\displaystyle AB,\;BC,\;CD,\;DE\)CD and DE join the remaining vertices without creating a cycle, so all five vertices are connected
4. \(\displaystyle 2+3+5+6=16\)The minimum spanning-tree total is 16

Common mistakes

Difficulty levels

Questions about this topic

In this chapter