edu.princeton.cs.algs4

## Class BoruvkaMST

• Object
• edu.princeton.cs.algs4.BoruvkaMST

• ```public class BoruvkaMST
extends Object```
The `BoruvkaMST` 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 Boruvka's algorithm and the union-find data type. 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`, `PrimMST`, and `KruskalMST`.

Author:
Robert Sedgewick, Kevin Wayne
• ### Constructor Summary

Constructors
Constructor and Description
`BoruvkaMST(EdgeWeightedGraph G)`
Compute a minimum spanning tree (or forest) of an edge-weighted graph.
• ### Method Summary

All 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 `BoruvkaMST` data type.
`double` `weight()`
Returns the sum of the edge weights in a minimum spanning tree (or forest).
• ### Methods inherited from class Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### BoruvkaMST

`public BoruvkaMST(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 `BoruvkaMST` data type.
Parameters:
`args` - the command-line arguments