The PrimMST 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 Edges property returns its edges.

This implementation uses Prim's algorithm with an indexed binary heap. 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 property takes constant time and the Edges method takes time proportional to V.

For alternate implementations, see , , and .