The KruskalMST 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() property returns the weight of a minimum spanning tree and the Edge() property returns its edges.

This implementation uses Krusal's algorithm and the union-find data type. The constructor takes time proportional to E log E 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 property takes constant time and the Edges method takes time proportional to V.

For alternate implementations, see , , and .