Kruskal's Algorithm

Spotting one

Same family as Prim. Connect everything, every link has a price, make the total as small as possible.

Reach for Kruskal when the links arrive as a list you can sort, when most pairs cannot be joined directly, or when the question asks which links end up being used.

The whole idea in one line

Sort every possible link from cheapest to dearest, walk the list, and keep a link only if the two things it joins are not already connected.

That second half is where the difficulty lives. You need a fast way to ask are these two already joined, and that's exactly what union-find is for. Read that page first if you haven't.

Where to start

Min Cost to Connect All Points. The twist is that nobody gives you the prices. You get positions on a map and have to work out every pair yourself before there is anything to sort.

Then Number of Operations to Make Network Connected, which is really a counting question. If the machines sit in four separate islands you need three cables, so the answer is islands minus one and the work is counting islands.

Find Critical and Pseudo-Critical Edges and Remove Max Number of Edges are both a big step up and assume the basic method is automatic. Leave them until it is.

Common mistakes

Sorting only part of the list. Kruskal is correct because it always considers the cheapest remaining link next. Break that and it stops working.

Adding a link that closes a loop. If both ends are already connected, it costs money and buys nothing.

Writing a slow check for are these connected that walks the network every time. Right answer, far too slow on anything large.