public class PrimMST extends Object
PrimMST
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 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).
This 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.
For additional documentation,
see Section 4.3 of
Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
For alternate implementations, see LazyPrimMST
, KruskalMST
,
and BoruvkaMST
.
Constructor and Description |
---|
PrimMST(EdgeWeightedGraph G)
Compute a minimum spanning tree (or forest) of an edge-weighted 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
PrimMST data type. |
double |
weight()
Returns the sum of the edge weights in a minimum spanning tree (or forest).
|
public PrimMST(EdgeWeightedGraph G)
G
- the edge-weighted graphpublic Iterable<Edge> edges()
public double weight()
public static void main(String[] args)
PrimMST
data type.args
- the command-line arguments