LazyPrimMST (Algorithms 4/e)

Object
- edu.princeton.cs.algs4.LazyPrimMST

```
public class LazyPrimMST
extends Object
```
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 Θ(E log E) 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 Θ(E) extra space in the worst case (not including the edge-weighted graph).
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.

Author:

Robert Sedgewick, Kevin Wayne

Constructor Summary

Constructors
Constructor Description

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

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method	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).

Methods inherited from class java.lang.Object
clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - LazyPrimMST
```
public LazyPrimMST(EdgeWeightedGraph G)
```
    Compute a minimum spanning tree (or forest) of an edge-weighted graph.
    
    Parameters:
    
    G - the edge-weighted graph
- Method Detail
  - edges
```
public Iterable<Edge> edges()
```
    Returns the edges in a minimum spanning tree (or forest).
    
    Returns:
    
    the edges in a minimum spanning tree (or forest) as an iterable of edges
  - weight
```
public double weight()
```
    Returns the sum of the edge weights in a minimum spanning tree (or forest).
    
    Returns:
    
    the sum of the edge weights in a minimum spanning tree (or forest)
  - main
```
public static void main(String[] args)
```
    Unit tests the LazyPrimMST data type.
    
    Parameters:
    
    args - the command-line arguments