Maths: Kruskal vs Prim cage match!

Which algorithm should you use to find the minimum spanningtree? Let’s find out!

When it comes to Networks, one of the mad skills you’regoing to acquire this year is determining the minimum spanning tree of agiven network with weighted edges. There are two strong algorithms battlingit out for supremacy in this mathematical space, and now we’re going to look atboth of them to figure out which fighter we should be backing in the Octagon.

Or, you know, in the “forest” where these “trees” we want tospan minimally are standing.

Let’s talk about the forest/trees

What is this for? First, go and read this thing about graphs. It’ll make you feel better. Right, now you know what we’re aiming for – a minimal spanning tree is useful in a variety of real-world situations, such as building efficient computer networks or making sure a town’s water supply is getting that H2O to taps without wasting money, energy and… like… pipes and… washers. Here are the two algorithms for you to eyeball while totally forgetting how we just embarrassed ourselves with our lack of plumbing knowledge.  

Kruskal uses simpler data structures

Our man Joseph Kruskal was all about finding that edge ofthe least possible weight to connect any two trees in the forest.

Here’s how you do it:

Prim is for graphs with lots of edges

Bad boy Robert C. Prim was free-wheeling when it came tothese forests. “Start anywhere,” he’d say, “and grow the tree by one minimum-weightedge. Repeat until they’re all in, yo!” (This is not an exact quotation, soplease don’t use it in your assignments .)

And here’s the recipe: