The LazyPrimMST 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 a lazy version of Prim's algorithm with a binary heap of edges. The constructor takes time proportional to E log E and extra space (not including the graph) proportional to E, 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.

For alternate implementations, see , , and .