Minimum Spanning Trees (Kruskal & Prim Algorithms) (Leaving Cert Applied Maths): Revision Notes
Minimum Spanning Trees (Kruskal's & Prim's Algorithms)
What is a minimum spanning tree?
A minimum spanning tree (MST) is a special type of tree that connects all vertices in a weighted graph using the smallest possible total edge weight. Think of it as finding the cheapest way to connect all points in a network.
Understanding MSTs is crucial for network optimisation problems. Whether you're designing computer networks, planning road systems, or laying cables, MST algorithms help find the most efficient connections.
Key properties of minimum spanning trees:
- Connects all vertices in the graph
- Uses exactly n-1 edges for n vertices (this is always true for any tree)
- Has the minimum total weight of all possible spanning trees
- Contains no cycles (like all trees)
The graph above shows a weighted network with 7 vertices. Our goal is to find the cheapest way to connect all these vertices together.
Critical Rule: For any graph with n vertices, the minimum spanning tree will always have exactly n-1 edges. This is a fundamental property that applies to all trees, not just minimum spanning trees.
Kruskal's algorithm
Kruskal's algorithm is a greedy approach that builds the minimum spanning tree by considering all edges in the graph and selecting them in order of increasing weight, while avoiding cycles.
How Kruskal's algorithm works
The algorithm follows these steps:
- List all edges in ascending order of weight
- Start with an empty tree
- Add the smallest edge that doesn't create a cycle
- Repeat step 3 until all vertices are connected
Kruskal's algorithm is called a greedy algorithm because at each step, it makes the locally optimal choice (smallest available edge) without considering future consequences. Remarkably, this greedy approach guarantees the globally optimal solution for MSTs.
Worked example using Kruskal's algorithm
Worked Example: Finding MST using Kruskal's Algorithm
Let's work through our example graph step by step:
Step 1: Organise edges by weight
First, we list all edges in ascending order of their weights:
Step 2: Build the tree systematically
We start by selecting the smallest edge (AB with weight 10), then continue adding edges that don't create cycles:
After adding AB (10) and FG (12), we have our first two edges selected.
Step 3: Continue adding edges
Next, we can add DE (14) without creating a cycle:
Step 4: Check for cycles before adding edges
When we reach DF (18) in our sorted list, adding it would create a cycle since D and F are already connected through other vertices. So we cross it out and move to the next edge.
Step 5: Complete the minimum spanning tree
Our final minimum spanning tree includes edges: AB (10), FG (12), DE (14), EG (16), CF (22), AC (25).
Total weight:
Notice that our tree has exactly 6 edges for 7 vertices .
Prim's algorithm
Prim's algorithm takes a different approach. Instead of considering all edges globally, it grows the minimum spanning tree from a starting vertex by always choosing the cheapest edge that connects to a new vertex.
How Prim's algorithm works
- Choose any starting vertex
- Create a table to track visited vertices and cumulative weights
- Find the cheapest edge from any visited vertex to any unvisited vertex
- Add that edge and vertex to the tree
- Repeat until all vertices are visited
Unlike Kruskal's algorithm which looks at all edges globally, Prim's algorithm grows the tree locally from a single starting point. You can start with any vertex - the final MST will be the same regardless of your starting choice.
Real-world example: telecommunications network
Real-World Example: Telecommunications Network Design
A telecommunications company needs to connect six Irish towns with fibre optic cable at €10,000 per kilometre. Let's use Prim's algorithm to find the minimum cost.
Step-by-step solution:
Starting with Mallow as our arbitrary first vertex:
We systematically add the cheapest connection at each step:
Final result:
The minimum spanning tree connects all towns with a total distance of 185 km, giving us a total cost of .
Prim's algorithm using distance matrices
Sometimes network data is presented as a distance matrix rather than a graph diagram. Prim's algorithm can still be applied using a systematic matrix approach.
Matrix method steps
Matrix Method Example: Step-by-Step Process
Starting with a distance matrix, we follow these steps:
- Choose starting vertex and delete its row
- Mark the column with the vertex number
- Find minimum weight in marked columns
- Add corresponding edge to MST
- Repeat until all vertices are included
Through systematic elimination and selection, we build our minimum spanning tree:
Final MST has total weight:
Key differences between the algorithms
Understanding the Algorithmic Approaches
Both algorithms are greedy algorithms that guarantee optimal solutions, but they work in fundamentally different ways:
Kruskal's Algorithm:
- Global approach - considers all edges at once
- Edge-focused - sorts edges by weight first
- Good for sparse graphs (few edges)
- Processes edges in strict weight order
Prim's Algorithm:
- Local approach - grows tree from one starting point
- Vertex-focused - expands from visited vertices
- Good for dense graphs (many edges)
- Can start from any vertex
Uniqueness of MST: When all edge weights are distinct (no ties), both algorithms will always produce the same unique minimum spanning tree. If there are ties in edge weights, multiple MSTs with the same total weight may exist.
Exam tips
Essential Exam Guidelines:
- Always check your edge count: n vertices need exactly n-1 edges
- Show your working: List edges in order and cross out rejected ones
- Watch for cycles: In Kruskal's, if both vertices of an edge are already connected, skip it
- Calculate total weight: Add up all selected edge weights for your final answer
- Real-world problems: Remember to multiply distance by cost per unit for final monetary answers
- Algorithm choice: Both give the same result, so choose whichever you're more comfortable with
Remember!
Key Points to Remember:
- Minimum spanning trees connect all vertices with minimum total weight
- For n vertices, you need exactly n-1 edges in your spanning tree
- Kruskal's algorithm sorts all edges first, then adds smallest non-cycle-creating edges
- Prim's algorithm grows the tree locally from a starting vertex
- Both algorithms are greedy and will find the optimal solution
- When edge weights are distinct, the MST is unique
- Real-world applications include network design, infrastructure planning, and cost optimisation