Kruskal's MST Algorithm Using Union-Find Data Structure

$\mathtt{REFERENCE}$ @ Source Class Notes

Kruskal's Algorithm

1. Like Prim's Algorithm, it is also a greedy algorithm.
2. While Prim's Algorithm starts from single node and keep growing to reach a final tree, this algorithm starts with $|V|$ trees and keep on combining to finally reach the MST.

Main Features

1. It starts with a forest of size $n = |V|$ trees.
2. At each step, it combines two trees to obtain a bigger tree and reduces the number of tress in the forest by 1.
3. When the forest has a single tree, it is a Minimum Spanning Tree (MST).

Use Union-Find data structure to make it faster.

Formal Sketch of Kruskal's MST Algorithm

1. $A = \phi$ // A is an empty forest
2. Sort the edges in the graph in increasing order of the weight.
3. for each edge $(u,v) \in G.E$ in increasing order of weight {
   1. if $u$ and $v$ are not already connected (find by using Union-Find) {
      1. $A = A \cup \{(u,v)\}$
      2. UNION(u,v) // Union-Find operation
      }
   }
4. return A

Implementation

Following is the implementation of above explanation.

Complexity

• Sorting takes $O(|E|log|E|)$ times
• Union-Find operations can be done in $O(log|V|)$ time if properly implemented

$\therefore$ The Time Complexity of this method will be $O(|E|log|E|)$ time.

for dense graph, $|E| \approx |V|^2 \Rightarrow$ SLOW
for sparse graph, $|E| \approx |V| \Rightarrow$ FAST

---

---

---