## DEV Community is a community of 871,998 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

JB

Posted on • Updated on

# Minimum Spanning Tree (Kruskal's Algorithm)

## Resources:

This post requires knowledge of graphs and union-find (covered in earlier posts).

Takeaways:

• A Minimum Spanning Tree (MST) is a subset of edges of an undirected, connected, weighted graph.
• This means a MST connects all vertices together in a path that has the smallest total edge weight.
• One algorithm for finding the MST of a graph is Kruskal's Algorithm.
• Kruskal's algorithm is a greedy algorithm - this means it will make locally optimum choices, with an intent of finding the overall optimal solution.
• Kruskal's algorithm relies on the union-find data structure.
• First the algorithm sorts the graph's edges in ascending order (by weight).
• Then for every edge, if it's vertices have different root vertices (determined by union-find's `Find()`), it will add the edge to a list & `Union()` it's vertices within the union-find data structure.
• If roots are the same, it will skip the edge.
• The final list represents the MST of the graph.
• Another common algorithm for finding the MST of a graph is Prim's Algorithm. Commonly, Prim's uses a heap or priority queue in it's implementation.
• Time complexity for Kruskal's algorithm is `O(e log v)` where `e` is the number of edges and `v` is the number of vertices in the graph. Space is `O(e + v)`.

Below is my implementation of Kruskal's algorithm:

As always, if you found any errors in this post please let me know!