CS Level Up Series (30 Part Series)
This post requires knowledge of graphs and union-find (covered in earlier posts).
- Kruskal's algorithm video explanation
- Another video explanation
- OO implementation of Kruskal's
- Wikipedia article on Minimum Spanning Tree
- 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
eis the number of edges and
vis 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!