public class LazyPrimMST extends Object
LazyPrimMSTclass 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.
weight() method takes constant time
edges() method takes time proportional to V.
|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 LazyPrimMST(EdgeWeightedGraph G)
G- the edge-weighted graph
public double weight()
public static void main(String args)
args- the command-line arguments