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

**It’s the best walk-through of the algorithm I have found thus far.**

*right now.*# Explanation

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`A`

to`C`

through`B`

.

In this hypothetical situation,*Note:*`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*.

# 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.