Hey everyone! I'm back with another Graph tutorial. This time, I plan to discuss Kruskal's Algorithm.
Kruskal's Algorithm is one of a few algorithms (we'll get to the rest later) for finding an undirected graph's Minimum Spanning Tree (MST).
A Minimum Spanning Tree is a tree connecting all nodes of a graph. Any node is reachable from any other node, and the total cost of traveling from one node in this MST to another is minimized.
I strongly recommend that you go watch this video right now. It's the best walk-through of the algorithm I have found thus far.
Alright, now that you've seen the video, you should get the gist of what's to be done here:
- Sort the edges by weight.
- Pick the lightest edge (the one with the smallest weight) and add that to the tree.
- Pick the next smallest edge and add it to the tree. It doesn't have to be connected to either of the nodes connected by the first edge (step 2).
- Keep picking the next smallest edge that doesn't create a cycle. If we already have
A => B and
B => C, we do not want to add
A => C, since we can already go from
Note: In this hypothetical situation,
A => B and
B => C both have edge weights equal to or less than
A => C, so adding
A => C instead of one of the other edges increases the cost of our tree, meaning it would no longer be the Minimum Spanning Tree.
- Once we have one tree, which includes all of a graph's nodes, we have arrived at the Minimum Spanning Tree.
I hope that I explained the rough process well enough. If not, re-read the entire article, and watch the video one more time. If you're still having troubles after that, post a comment and I'll help you out.
Oh, and don't worry about the pseudo-code at the end of the video... It's confusing, and the narrator doesn't discuss all the aspects of it. Next time, I'll walk through a code implementation of this algorithm, which'll be more clear than that pseudo-code.