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