Implementation of Kruskal's Algorithm

Implementation Notes

During Kruskal’s algorithm, we’ll iteratively build up a minimum spanning tree $T$ by processing the edges one by one. For each edge $e = (u, v)$ we need to check whether $u$ and $v$ are already connected in $T$. The main challenge of implementing Kruskal is performing it efficiently.

The naive approaches, such as running a BFS from $u$ to $v$ for each edge, would be quite costly. The key component in speeding up the algorithm is using the correct data structure, which is called Disjoint-Set-Union (DSU) or Union-Find.

As the name suggests, a DSU data structure stores disjoint sets. In our case, it will store the connected components of our current graph $T$. Each set has a representative. We can efficiently check whether two elements are in the same set by comparing their representatives.

Here is an illustration of a DSU data structure containing the three disjoint sets $\{a, b, c\}, \{d, e\}$ and $\{f\}$. The representative of each set is marked in gray.