Graph Algorithms (Part 3.0): Kruskal's MST [Concept]

Algorithms
, , ,
1

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.

Explanation

Alright, now that you’ve seen the video, you should get the gist of what’s to be done here:

  1. Sort the edges by weight.
  2. Pick the lightest edge (the one with the smallest weight) and add that to the tree.
  3. 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).
  4. 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 A to C through B.
    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.
  5. Once we have one tree, which includes all of a graph’s nodes, we have arrived at the Minimum Spanning Tree.

Conclusion

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.

@oaktree out.

3 Likes
2

This topic was automatically closed after 30 days. New replies are no longer allowed.