Growing one tree
Prim’s algorithm finds a minimum spanning tree by growing a single tree outward from a starting vertex. At every step it looks only at the edges with one end in the tree and the other end outside it, and it takes the cheapest of them. That edge brings one new vertex into the tree.
The network is the same five towns as before, with eight possible roads. Start at A. The edges leaving the tree are AB, weight 4, and AC, weight 2.
The tree starts as the single town A, in gold. Only AB and AC leave it.
Step by step
The cheaper edge at A is AC, weight 2, so C joins the tree.
Now the tree is A and C. The edges leaving it are AB 4, BC 5, CE 3 and CD 8. The cheapest is CE, so E joins.
The tree is A, C and E. The edges leaving it are AB 4, BC 5, CD 8, DE 7 and BE 9. The cheapest is AB, so B joins.
Only D is outside. The edges reaching it are BD 6, DE 7 and CD 8, so BD is taken. The tree is AC, CE, AB and BD, with total weight 2 + 3 + 4 + 6 = 15. It is the same tree Kruskal’s algorithm builds, with the same total.
The tree from A in gold. The numbers give the order in which the towns join: C, E, B, then D. The total is 2 + 3 + 4 + 6 = 15.
Any starting vertex
Prim may start anywhere. From D, the edges at D are BD 6, DE 7 and CD 8, so B joins first. Then AB 4 brings in A, AC 2 brings in C, and CE 3 brings in E. The edges are taken in a different order, but they are the same four edges, and the total is again 15.
This is no accident. When every weight in a network is different, it has exactly one minimum spanning tree, so every starting vertex, and Kruskal’s algorithm too, must find that same tree. When some weights are equal, different starts can give different trees, all with the same least total.
Started from D, the towns join in the order B, A, C, E, and the gold tree is the same one, with total 15.
The matrix method
When the network is given as a weighted table, Prim’s algorithm runs on the table itself. A dash means that no road joins those two towns. The rule is the same, written for rows and columns: the rows of the towns in the tree are the edges leaving them, and crossing out a column removes the edges into a town already in the tree.
Start at A: cross out column A, and scan row A. Its entries are 4 under B and 2 under C. The smallest is 2, so circle it, and C joins the tree. This is the edge AC.
The weighted table of the five towns. In row A the smallest entry is 2, in column C.
Scanning every row of the tree
Cross out column C. Now scan rows A and C together, in the columns that are left, B, D and E. Row A gives 4, and row C gives 5, 8 and 3. The smallest is 3, in row C and column E, so E joins by the edge CE.
Cross out column E and scan rows A, C and E in columns B and D. The entries are 4 in row A; 5 and 8 in row C; and 9 and 7 in row E. The smallest is 4, in row A and column B, so B joins by AB.
Cross out column B. Only column D is left, and rows A, B, C and E give —, 6, 8 and 7 in it. The smallest is 6, in row B, so D joins by BD. Every column is crossed out, and the circled entries 2, 3, 4 and 6 total 15.
The part of the table still scanned once A and C are in the tree: rows A and C, columns B, D and E. The smallest entry is 3, in row C, column E.
With E in the tree too: rows A, C and E, columns B and D. The smallest entry is 4, in row A, column B.
Only column D is left. The smallest entry is 6, in row B, so the last edge is BD.
No cycle check needed
Every edge Prim takes has one end outside the tree, so it can never close a cycle. Kruskal has to test each edge for a cycle; Prim does not, and it needs no sorted list of edges either. That is why it suits a table, and a computer, so well.
The usual mistakes
Scanning only the row of the town that joined last. After E joins, row E offers 9 and 7, but row A still offers 4, and that is the smallest. Every row of the tree is scanned at every step.
Starting with the cheapest edge in the whole network. That is how Kruskal begins. Prim from A must begin with an edge at A.
Reading an entry in a crossed-out column. At the last step row B still shows 5 under C, which is less than 6, but column C is crossed out: BC joins two towns already in the tree, and it would close the cycle A-B-C.
Expecting Prim and Kruskal to give different totals. Both find a minimum spanning tree, and the least total is one number.
Pipes and cables
In the first application below, a farmer plans water pipes from a pump to five fields using a table of distances. In the second, a wind farm’s cable network is planned from the substation, and then planned again when a new turbine is approved.
Worked example: Irrigation Pipes From a Farm's Pump to Five Fields, Planned From a Table of Distances
Question A farmer will lay water pipes so that the pump P supplies five fields A, B, C, D and E, each field fed straight from the pump or through the pipes to other fields. The table gives the length in meters of the pipe needed between each pair of sites: P–A 42, P–B 55, P–C 70, P–D 38, P–E 64, A–B 30, A–C 48, A–D 50, A–E 36, B–C 40, B–D 61, B–E 57, C–D 39, C–E 52, D–E 33. No two lengths are equal. (a) Use Prim's algorithm, starting at the pump, to find the order in which the fields are joined, the pipe that joins each one, and the least total length of pipe. (b) Her first plan was a separate pipe from the pump to each field. How much pipe does the network from (a) save compared with that plan?
1.Start at the pump. The shortest entry in P's row is P–D, 38 m, so D is joined first.
The shortest entry in the pump's row is P–D, 38 m. Each pipe is ringed in the row of the field it joins. 2.From P and D, the pipes to new fields are P–A 42, P–B 55, P–C 70, P–E 64, D–A 50, D–B 61, D–C 39 and D–E 33. The shortest is D–E, so E is joined second.
From P and D, the shortest pipe to a new field is D–E, 33 m. 3.From P, D and E, the shortest pipe to a new field is E–A, 36 m, shorter than D–C at 39 m, so A is joined third. From P, D, E and A, the shortest is A–B, 30 m, so B is joined fourth.
Then E–A, 36 m, and A–B, 30 m. 4.Only C is left. Its pipes to joined sites are D–C 39, B–C 40, A–C 48, C–E 52 and P–C 70, so C is joined by D–C. (a) The order is D, E, A, B, C, by the pipes P–D, D–E, E–A, A–B and D–C, with a total of 38 + 33 + 36 + 30 + 39 = 176 m.
(a) C joins by D–C, 39 m, not B–C at 40 m. The total is 176 m. 5.A separate pipe from the pump to each field needs 42 + 55 + 70 + 38 + 64 = 269 m. (b) The network saves 269 − 176 = 93 m of pipe.
(b) Separate pipes from the pump need 269 m, so the network saves 93 m.
Answer: (a) D by P–D, E by D–E, A by E–A, B by A–B, C by D–C; the total is 176 m. (b) 93 m
Common mistakes
- Looking only in the row of the field joined last. From B the shortest pipe to C is 40 m, but D was joined earlier and D–C is 39 m: Prim's algorithm compares the rows of every site already joined.
- Starting with the shortest pipe in the whole table, A–B at 30 m. That is how Kruskal's algorithm begins; Prim's algorithm from the pump must begin with a pipe at the pump.
More spanning trees and route problems problems, worked step by step →
Worked example: Cables Between a Wind Farm's Substation and Four Turbines, and a Fifth Turbine Approved Before Building Starts
Question A wind farm will join its substation S and four turbines A, B, C and D with underground cable. Each turbine must be linked to the substation directly or through other turbines, and cables can meet only at a turbine or at the substation. The cable routes that can be used, with lengths in meters, are S–A 400, S–B 650, A–B 500, A–C 700, B–C 450, B–D 800 and C–D 550. (a) Use Prim's algorithm, starting at S, to find the order in which the turbines are joined and the least total length of cable. (b) Before any cable is laid, a fifth turbine N is approved. It can be joined to B by 350 m, to C by 300 m and to D by 250 m of cable. What is the least total length of cable for all six sites now?
1.From S, the routes are S–A 400 m and S–B 650 m. The shorter is S–A, so A is joined first.
From S, the shorter route is S–A, 400 m. 2.From S and A, the routes to new turbines are S–B 650, A–B 500 and A–C 700, so A–B joins B. From S, A and B, the shortest is B–C, 450 m, so C is joined next, and then C–D (550 m, against B–D at 800 m) joins D.
Then A–B, B–C and C–D, each the shortest route from the sites already joined. 3.(a) The order is A, B, C, D, and the least total length is 400 + 500 + 450 + 550 = 1900 m.
(a) The order is A, B, C, D, and the total is 1900 m. 4.With N, run the algorithm again from S. It takes S–A and A–B as before. From S, A and B the shortest route is now B–N, 350 m. From these four sites the shortest is N–D, 250 m, and then N–C, 300 m, which is shorter than B–C at 450 m.
With N, the algorithm takes S–A and A–B, then B–N, N–D and N–C. 5.(b) The least total length is 400 + 500 + 350 + 250 + 300 = 1800 m. Check: the five cables join all six sites without a cycle, and the new plan drops B–C and C–D (1000 m) for B–N, N–C and N–D (900 m), so it is 100 m shorter than the plan for four turbines.
(b) The least total is 1800 m.
Answer: (a) A, B, C, D, with a total of 1900 m; (b) 1800 m
Common mistakes
- Keeping the network from (a) and adding N by its shortest cable, N–D at 250 m, to get 1900 + 250 = 2150 m. Nothing has been laid yet, so the whole network is planned again, and routing through N replaces two longer cables.
- Rejecting 1800 m because six sites should need more cable than five. Cables may meet at N, and N sits close to B, C and D, so its three short cables together are shorter than B–C and C–D.
More spanning trees and route problems problems, worked step by step →