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:
YOU MIGHT ALSO LIKE:
Nov 23, 2020
Build little breaks into your study routine
It’s easy to get locked into your desk chair for long periods of time. Here are some ways to make sure you take a little break from your study. Just don’t go too far in the other direction – you still gotta smash through that work! The best way to have a break is to…
Oct 14, 2020
What to eat during last-minute study sessions
Rewarding yourself, or if we’re being more honest here – bribing yourself with snacks is a long-standing and reputable study hack. The idea is that after every paragraph or page you read, you will find a sour worm staring up into your tired eyes. You pick it up, dust the sugar off your stained-yellow textbook…
Oct 12, 2020
Learn how to learn, learners
Learning is a tricky process with so many things to account for. It’s so easy to find yourself overwhelmed as you fumble your way through various textbooks, journals and crash course YouTube videos. You have things like time constraints to manage, resources to compete for and even biological issues such as The Forgetting Curve. While…