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 1 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 2 .

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.

Footnotes:

1. Incidentally, Prim’s algorithm was discovered by Jarnik, and rediscovered independently by Dijkstra

2. Because it’s unique