Prim's Algorithm

Spotting one

The question almost never says minimum spanning tree. It says connect every city, or every house, or every machine. Each connection has a price, and you want the smallest total.

Three things together mean Prim: everything has to end up connected, every possible link has a cost, and nobody asks about the route between two particular places. Only the total matters.

That last one is the one people miss. If you're asked for the cheapest way to get from A to B, that's a shortest path question and Prim is the wrong tool. You want Dijkstra.

Prim or Kruskal?

Both give the same total. Pick Prim when almost every pair of points can be joined, because it grows outward from one place and never has to look at the whole list of links. Pick Kruskal when links are few, when they arrive already sorted by price, or when you also need to say which links were used.

Where to start

Connecting Cities With Minimum Cost first. The prices are handed to you, so the only thing being tested is the method.

Then Optimize Water Distribution in a Village. It looks like two different costs, wells and pipes, until you notice that digging a well is just laying a pipe to an imaginary extra house. Inventing a node so two costs become one kind of cost is a trick worth keeping.

Common mistakes

Comparing the total distance back to the start out of habit. Prim only ever compares the price of the next single link.

Forgetting to skip points that are already connected, which quietly builds a loop.