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

Minimum spanning trees

A minimum connector joins all vertices with no cycle and least total edge weight. Prim’s algorithm grows one tree by repeatedly selecting the lightest edge crossing from reached to unreached vertices

1. Use n minus 1 edges A tree with n vertices has exactly n minus 1 edges \(\displaystyle n=5\Rightarrow |E(T)|=n-1=4\)
2. Grow from the current tree Prim's algorithm selects the lightest edge joining a tree vertex to a vertex outside the tree \(\displaystyle T=\{A\},\quad w(AB)=3<w(AC)=6\Rightarrow AB\)
3. Keep the current cut An eligible edge has exactly one endpoint in the reached set. An internal edge creates a cycle; a detached edge does not grow the current tree. Among eligible edges, choose a minimum weight
4. Add the selected weights The minimum spanning-tree total is the sum of the weights in the selected tree \(\displaystyle W(T)=\sum_{e\in T}w(e)\)

Worked example

A network has vertices A, B, C, D and E with the edge weights shown below. Use Prim’s algorithm starting at A to find the minimum spanning-tree total

1. \(\displaystyle T=\{A\},\quad AB:2<AC:4\)The eligible links from A are AB and AC. Select AB and reach B
2. \(\displaystyle T=\{A,B\},\quad BC:3<AC:4<BD:7\)Select BC. AC is now internal to the reached set and is no longer an eligible crossing edge
3. \(\displaystyle T=\{A,B,C\},\quad CD:5<BD:7<CE:8\)Select CD, then select DE of weight 6 rather than CE of weight 8 to reach E
4. \(\displaystyle 2+3+5+6=16\)Four selected edges connect all five vertices without a cycle, with minimum total 16

Common mistakes

Difficulty levels

Questions about this topic

In this chapter