The BoruvkaMST class represents a data type for computing a Minimum spanning tree in an edge-weighted graph. The edge weights can be positive, zero, or negative and need not be distinct. If the graph is not connected, it computes a Minimum spanning forest, which is the union of minimum spanning trees in each connected component. The Weight method returns the weight of a minimum spanning tree and the Edges() method returns its edges.

This implementation uses Boruvka's algorithm and the union-find data type.

The constructor takes time proportional to E log V and extra space (not including the graph) proportional to V, where V is the number of vertices and E is the number of edges. Afterwards, the weight() method takes constant time and the edges() method takes time proportional to V.