public class LazyPrimMST extends Object
LazyPrimMST
class represents a data type for computing a
minimum spanning tree in an edgeweighted 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 additional documentation,
see Section 4.3 of
Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
For alternate implementations, see PrimMST
, KruskalMST
,
and BoruvkaMST
.
Constructor and Description 

LazyPrimMST(EdgeWeightedGraph G)
Compute a minimum spanning tree (or forest) of an edgeweighted graph.

Modifier and Type  Method and Description 

Iterable<Edge> 
edges()
Returns the edges in a minimum spanning tree (or forest).

static void 
main(String[] args)
Unit tests the
LazyPrimMST data type. 
double 
weight()
Returns the sum of the edge weights in a minimum spanning tree (or forest).

public LazyPrimMST(EdgeWeightedGraph G)
G
 the edgeweighted graphpublic Iterable<Edge> edges()
public double weight()
public static void main(String[] args)
LazyPrimMST
data type.args
 the commandline arguments