public class PrimMST extends Object
PrimMSTclass 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 Prim's algorithm with an indexed binary heap. The constructor takes Θ(E log V) time in the worst case, where V is the number of vertices and E is the number of edges. Each instance method takes Θ(1) time. It uses Θ(V) extra space (not including the edge-weighted graph).
weight() method correctly computes the weight of the MST
if all arithmetic performed is without floating-point rounding error
or arithmetic overflow.
This is the case if all edge weights are non-negative integers
and the weight of the MST does not exceed 252.
|Constructor and Description|
Compute a minimum spanning tree (or forest) of an edge-weighted graph.
|Modifier and Type||Method and Description|
Returns the edges in a minimum spanning tree (or forest).
Unit tests the
Returns the sum of the edge weights in a minimum spanning tree (or forest).
public PrimMST(EdgeWeightedGraph G)
G- the edge-weighted graph
public double weight()
public static void main(String args)
args- the command-line arguments