← Graphs and Networks › Minimum Spanning Trees
Minimum Spanning Trees
Key Terms
- A spanning tree of a connected graph: a subgraph that is a tree connecting all n vertices, using exactly n−1 edges
- A minimum spanning tree (MST): the spanning tree with the smallest total edge weight
- Prim’s algorithm
- grow the tree one vertex at a time, always adding the cheapest edge that connects a new vertex
- Kruskal’s algorithm
- sort all edges by weight, add edges in order, skip any that create a cycle
- Both algorithms always produce the same total weight (though the tree may differ if weights are equal)
Prim’s Algorithm:
1. Start at any vertex
2. Add the shortest edge connecting the tree to a new (unvisited) vertex
3. Repeat until all vertices are included
Kruskal’s Algorithm:
1. List all edges in order from smallest to largest weight
2. Add each edge to the tree, unless it creates a cycle
3. Stop when n−1 edges have been added
1. Start at any vertex
2. Add the shortest edge connecting the tree to a new (unvisited) vertex
3. Repeat until all vertices are included
Kruskal’s Algorithm:
1. List all edges in order from smallest to largest weight
2. Add each edge to the tree, unless it creates a cycle
3. Stop when n−1 edges have been added
Worked Example: Find the MST of: edges AB=4, AC=2, BC=6, BD=3, CD=5 (5 vertices: A, B, C, D).
Kruskal’s: Sort edges: AC=2, BD=3, AB=4, CD=5, BC=6
Add AC (no cycle) → Add BD (no cycle) → Add AB (no cycle; now A,B,C,D all connected) → STOP (3 edges for 4 vertices)
MST edges: AC, BD, AB Total weight = 2 + 3 + 4 = 9
Kruskal’s: Sort edges: AC=2, BD=3, AB=4, CD=5, BC=6
Add AC (no cycle) → Add BD (no cycle) → Add AB (no cycle; now A,B,C,D all connected) → STOP (3 edges for 4 vertices)
MST edges: AC, BD, AB Total weight = 2 + 3 + 4 = 9
Hot Tip: A MST connects all vertices with minimum total cost — used for designing networks (power lines, fibre optic cables, water pipes) where you want to connect all points as cheaply as possible. Unlike shortest path, MST isn’t about getting from A to B; it’s about connecting everything.
What Is a Spanning Tree?
A spanning tree of a connected graph is a subgraph that:
- Contains all vertices of the original graph
- Is connected
- Has no cycles (it is a tree)
A minimum spanning tree (MST) is the spanning tree whose total edge weight is as small as possible. This is the answer to: “what is the cheapest way to connect all these points?”
Prim’s Algorithm
Start at any vertex and grow the tree greedily:
- Choose any starting vertex. Mark it as “in the tree.”
- Among all edges from “in-tree” vertices to “not-in-tree” vertices, select the one with minimum weight.
- Add the selected edge and its new vertex to the tree.
- Repeat until all vertices are in the tree.
Kruskal’s Algorithm
- Sort all edges from smallest to largest weight.
- Go through the sorted list. Add each edge to the MST unless doing so would create a cycle (i.e. both endpoints are already in the tree).
- Stop when you have n−1 edges (where n is the number of vertices).
Kruskal’s is often easier to apply when the edge list is small; Prim’s is better for dense graphs.
Strategy: Always verify at the end that your MST has exactly n−1 edges and that all n vertices are included. If not, you made an error somewhere.
Mastery Practice
- Fluency A graph has 4 vertices and a spanning tree. How many edges does the spanning tree have?
- Fluency Using Kruskal’s algorithm, find the MST for the graph with edges: AB=5, AC=3, BC=8, BD=2, CD=6. List the edges selected and the total weight.
- Fluency Using Prim’s algorithm starting at vertex A, find the MST for: AB=7, AC=4, AD=2, BC=3, CD=5. Show each step.
- Fluency A spanning tree of a graph with 6 vertices is found. It has edges with weights 3, 5, 2, 8, 4. What is the total weight of the spanning tree?
- Understanding A telecommunications company wants to lay cable to connect 5 suburbs (A–E). The cost (thousands of dollars) to directly connect each pair is: AB=10, AC=6, AD=15, AE=20, BC=4, BD=8, BE=12, CD=9, CE=7, DE=11. Use Kruskal’s algorithm to find the minimum cost network and the total cost.
- Understanding Apply Prim’s algorithm starting at vertex P to the graph: PQ=8, PR=5, PS=12, QR=7, QS=6, RS=4, ST=3, QT=9, RT=10. Find the MST and its total weight.
- Understanding A graph has 5 vertices with the following sorted edge weights (smallest to largest): 1, 2, 3, 4, 5, 6, 7. Applying Kruskal’s algorithm, explain which edges would be skipped if adding them creates a cycle. How do you identify a cycle?
- Understanding The following network shows pipe lengths (metres) between pumping stations: 1–2=120, 1–3=80, 2–3=60, 2–4=90, 3–4=50, 3–5=110, 4–5=40, 4–6=70, 5–6=30. Find the minimum spanning tree and the minimum total pipe length needed to connect all 6 stations.
- Problem Solving A road network has 7 cities (A–G) with distances (km): AB=15, AC=10, AD=20, BC=8, BD=12, BE=18, CD=6, CE=14, DE=9, DF=22, EF=11, EG=16, FG=7.
- (a) Apply Kruskal’s algorithm to find the MST.
- (b) What is the minimum total road length to connect all 7 cities?
- (c) If the edge EG costs twice as much to build per km due to terrain, which edge would be removed from the MST and what would be the new total?
- Problem Solving A connected graph has 8 vertices. A student claims to have found the minimum spanning tree with a total weight of 45 using 7 edges. Another student finds a different set of 7 edges with a total weight of 43.
- (a) Which is the minimum spanning tree, and why?
- (b) Can both be valid spanning trees? Explain.
- (c) Is it possible for a graph to have more than one minimum spanning tree with the same total weight? Give an example or explain why not.