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 whose 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 tree .

### 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.

## MoreThanMaths

One for Y13 students RT @icecolbeveridge: [FCM] Prim vs Kruskal: http://t.co/HQVyqxVzpO

## Dragon_Dodo

.@icecolbeveridge I like Prim’s algorithm, and I like Kruskal’s algorithm. But which is better? There’s only one way to find out… FIGHT!

## MathbloggingAll

Prim vs Kruskal http://t.co/hRGvVJDFHC

## srcav

Love this from @icecolbeveridge Prim vs Kruskal http://t.co/q7Lzc1FkI1