Introduction

Welcome back to the Graph Algorithms series! A Minimum Spanning Tree (MST) connects every vertex of a weighted graph using the cheapest possible total edge weight, with no cycles.

Kruskal's Algorithm builds the MST greedily: it sorts the edges from cheapest to most expensive and adds each one, as long as it does not create a cycle. The trick for detecting cycles fast is a data structure called union-find (also known as disjoint-set).

The graph is undirected and weighted, given as n (vertices 0 to n - 1) and edges, a flat array of triples [u0, v0, w0, ...] for an undirected edge u - v of weight w.

Let's get started!