edu.princeton.cs.algorithms

Class LazyPrimMST

java.lang.Object

edu.princeton.cs.algorithms.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 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.4 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 and Description
LazyPrimMST(EdgeWeightedGraph G) Compute a minimum spanning tree (or forest) of an edge-weighted graph.

Method Summary

Methods

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).

Methods inherited from class java.lang.Object

clone, equals, finalize, 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.