Minimum Spanning Trees
Australian Gas Networks uses minimum spanning tree algorithms to plan new pipeline routes, minimising total pipe length directly reduces infrastructure spend. Two algorithms (Kruskal's and Prim's) always find the cheapest way to connect all nodes, even in networks with hundreds of edges.
Practise this lesson
Three printable worksheets that build from foundations to mastery, or build your own from any module’s questions.
A council needs to connect 5 parks with walking paths. The possible paths and their costs ($000s) are: A–B: 4, A–C: 2, B–C: 3, B–D: 6, C–D: 1, C–E: 5, D–E: 2. How would you minimise total cost?
Before reading onwrite your strategy.
A minimum spanning tree (MST) connects all vertices with minimum total edge weight. Both Kruskal's and Prim's algorithms always find the MST, they just build it differently.
Kruskal's algorithm: sort all edges by weight; add the cheapest edge that doesn't form a cycle; repeat until n−1 edges added.
Prim's algorithm: start at any vertex; always add the cheapest edge connecting the current tree to a new vertex; repeat until all vertices included.
Same total weight: both algorithms produce an MST with the same total weight (though possibly different structure if weights are equal).
Weighted network: a network where each edge has a numerical weight (cost, distance, time, etc.).
Key facts
- MST connects all vertices with minimum weight
- Kruskal's: sort edges, add cheapest non-cycle
- Prim's: grow tree from one vertex
Concepts
- Why both algorithms give same total weight
- When to use each algorithm
- Role of cycle detection in Kruskal's
Skills
- Apply Kruskal's to a weighted network
- Apply Prim's from a specified start vertex
- Calculate minimum total weight
Kruskal's algorithm steps:
- List all edges sorted from cheapest to most expensive.
- Add the cheapest edge to the tree.
- For each subsequent edge: if adding it does NOT create a cycle → add it. If it creates a cycle → skip it.
- Stop when you have $n-1$ edges.
How to check for a cycle: an edge creates a cycle if both its endpoints are already in the current tree and are already connected to each other (in the same component).
Add C–D(1) ✓. Add A–C(2) ✓. Add D–E(2) ✓. Add B–C(3) ✓, now 4 edges, all 5 vertices connected. Stop.
Total weight = 1+2+2+3 = 8.
Kruskal’s algorithm: sort all edges cheapest first. Add edges in order, skipping any that create a cycle. Stop when n−1 edges have been added. Quick for sparse networks; easy to track by sorting the edge list.
Pause, copy Kruskal's four steps: (1) list all edges sorted cheapest to most expensive; (2) add the cheapest edge that does not form a cycle; (3) repeat until n − 1 edges added; (4) skip any edge that would close a loop into your book.
We just saw Kruskal's algorithm: sort all edges globally from cheapest to most expensive, add edges in order skipping any that create a cycle, stop when n − 1 edges are added. That raises a question: Kruskal's requires sorting all edges at once, is there an alternative that grows the MST from a single starting vertex without needing the full sorted list? This card answers it → Prim's algorithm starts at any one vertex and at each step adds the cheapest edge that connects the current tree to a new unvisited vertex, growing one vertex at a time.
Prim's algorithm steps:
- Choose any starting vertex. It is now in the tree.
- Look at all edges connecting the current tree to vertices NOT yet in the tree.
- Add the cheapest such edge (and its new vertex) to the tree.
- Repeat steps 2–3 until all vertices are in the tree.
Key difference from Kruskal's: Prim's grows from a single starting point. Kruskal's picks edges globally regardless of location.
From A: cheapest edge to new vertex = A–C(2). Add C.
From {A,C}: cheapest = C–D(1). Add D.
From {A,C,D}: cheapest = D–E(2). Add E.
From {A,C,D,E}: cheapest = B–C(3). Add B. Done.
Total = 2+1+2+3 = 8 ✓ (same as Kruskal's)
Prim’s algorithm: start from any vertex. At each step, add the cheapest edge connecting the current tree to a new (unvisited) vertex. Stop when all vertices are included. Always grows one vertex at a time; easier for dense networks.
Pause, copy Prim's algorithm steps: (1) start at any vertex; (2) add the cheapest edge connecting the current tree to any unvisited vertex; (3) repeat until all vertices are included, always growing one new vertex at a time into your book.
We just saw Prim's algorithm growing the MST one vertex at a time by always choosing the cheapest edge to an unvisited vertex. That raises a question: Kruskal's and Prim's both find a minimum spanning tree, when do they give the same result, when can they differ, and how do you choose which to use in an exam? This card answers it → both always give the same minimum total weight; they may find different trees if tie edges exist; use Kruskal's when edges are already sorted or the network is sparse; use Prim's when starting from a specific vertex is required.
Both algorithms always produce a minimum spanning tree with the same total weight. The tree structure may differ if some edges have equal weights.
| Feature | Kruskal's | Prim's |
|---|---|---|
| Starting point | Any edge (globally) | Specific vertex |
| Sort required? | Yes, sort all edges | No, compare locally |
| Best when | Edge list given | Diagram given |
| Total weight | Same result | Same result |
Kruskal vs Prim: both always produce a minimum spanning tree with the same total weight. Kruskal: sort globally, better for sparse graphs. Prim: grow locally, better for dense graphs. If edge weights are distinct, both produce the same unique MST.
Pause, copy the Kruskal vs Prim comparison: both produce an MST with the same total weight; Kruskal sorts globally (better for sparse networks); Prim grows locally from one vertex (better for dense networks or when a start vertex is specified); both can give different trees when tie-weight edges exist into your book.
Worked examples · reveal each step
5 vertices A–E. Edges: A–B(8), A–C(3), B–C(5), B–D(7), C–D(2), C–E(6), D–E(4). Find the MST using Kruskal's.
Same network as Problem 1. Use Prim's algorithm starting at vertex A.
A pipeline network connects towns P, Q, R, S with costs (km): P–Q: 12, P–R: 8, Q–R: 5, Q–S: 10, R–S: 7. What is the minimum total pipeline length to connect all towns?
- Network: A–B(6), A–C(4), B–C(2), B–D(8), C–D(3), D–E(5). Use Kruskal's to find the MST and total weight.
- Use Prim's starting at vertex B for the same network. Do you get the same total weight?
- In Kruskal's, you try to add edge A–B but both A and B are already connected through C. What do you do?
- A network has 8 vertices. Its MST has total weight 24. Another student claims they found an MST with weight 22. Who is right? How do you check?
For the parks problem, the MST uses edges C–D(1), A–C(2), D–E(2), B–C(3), total cost $8,000. The strategy of "always choose the cheapest available connection" is exactly Kruskal's or Prim's, you may have instinctively applied the algorithm!
Q1. Kruskal's algorithm adds edges in order of:
Q2. Prim's algorithm always:
Q3. In Kruskal's algorithm, you skip an edge when:
Q4. A minimum spanning tree of a 7-vertex weighted network has how many edges?
Q5. If you apply both Kruskal's and Prim's to the same weighted connected network:
SA 1. Use Kruskal's algorithm to find the MST for: A–B(9), A–C(3), B–C(6), B–D(5), C–D(2), C–E(8), D–E(4). State which edges are in the MST and the total weight. (3 marks)
SA 2. A student is using Prim's algorithm. They are at step 3 and their current tree is {A, C, D}. Available edges to new vertices: A–B(9), C–B(6), D–B(5), D–E(4). Which edge should they add next? Justify. (2 marks)
Answers (click to reveal)
MC 1, A: Kruskal's sorts edges increasing weight.
MC 2, D: Prim's grows from a starting vertex.
MC 3, B: Skip when adding creates a cycle.
MC 4, C: 7−1=6 edges.
MC 5, A: Both produce the same total weight MST.
SA 1 (3 marks): Sorted correctly [1]; correct MST edges identified [1]; total weight = 14 [1].
SA 2 (2 marks): D–E(4) identified [1]; correctly justified as cheapest to new vertex [1].
Timed questions on Kruskal's and Prim's algorithms.
⚔ Enter the arenaMark lesson as complete
Tick when you've finished.