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 ((Incidentally, Prim’s algorithm was discovered by Jarnik, and rediscovered independently by Dijkstra)) 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 ((Because it’s unique)) .

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.