Prim vs Kruskal

-or-
The D in D1 stands for death match

A student asks:

How do you remember the difference between Prim’s algorithm and Kruskal’s algorithm?

In honesty, I don’t. This is one of the things that REALLY FRUSTRATES me about D1: it puts so much emphasis on remembering whose algorithm was whose1 ahead of figuring out how to program computers to solve problems. It’s like having a Great British Bake Off that’s all about how they plan to make cakes.

But that doesn’t answer the question, does it? Prim and Kruskal both give you a minimum spanning tree (MST) - the shortest set of edges that connect every node to every other. If the MST is unique, both are guaranteed to give the same tree2 .

Prim’s algorithm

Prim’s algorithm is the one where you start with a random node and keep adding the ‘nearest’ node that’s not part of the tree. That means you never have to worry about making a circuit, because you’re only ever adding nodes and edges that can’t complete one.

If you like, Prim’s algorithm grows like a primrose, starting from a seed and gradually spreading out.

Kruskal’s algorithm

You start Kruskal’s algorithm by sorting the edges by length, and adding them to the tree in order, shortest first - unless they create a circuit.

Kruskal’s algorithm is (to me) more chaotic than Prim’s - and it’s more complicated (like the word Kruskal is more complicated than the word Prim.)

So… that’s how I’d remember the difference, if I had to. Luckily, I don’t.

Colin

Colin is a Weymouth maths tutor, author of several Maths For Dummies books and A-level maths guides. He started Flying Colours Maths in 2008. He lives with an espresso pot and nothing to prove.

  1. Incidentally, Prim’s algorithm was discovered by Jarnik, and rediscovered independently by Dijkstra []
  2. Because it’s unique []

Share

4 comments on “Prim vs Kruskal

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Sign up for the Sum Comfort newsletter and get a free e-book of mathematical quotations.

No spam ever, obviously.

Where do you teach?

I teach in my home in Abbotsbury Road, Weymouth.

It's a 15-minute walk from Weymouth station, and it's on bus routes 3, 8 and X53. On-road parking is available nearby.

On twitter