Class BoruvkaMST
 Object

 edu.princeton.cs.algs4.BoruvkaMST

public class BoruvkaMST extends Object
TheBoruvkaMST
class represents a data type for computing a minimum spanning tree in an edgeweighted 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. Theweight()
method returns the weight of a minimum spanning tree and theedges()
method returns its edges.This implementation uses Boruvka's algorithm and the unionfind 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 edgeweighted graph).
This
weight()
method correctly computes the weight of the MST if all arithmetic performed is without floatingpoint rounding error or arithmetic overflow. This is the case if all edge weights are nonnegative integers and the weight of the MST does not exceed 2^{52}.For additional documentation, see Section 4.3 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. For alternate implementations, see
LazyPrimMST
,PrimMST
, andKruskalMST
. Author:
 Robert Sedgewick, Kevin Wayne


Constructor Summary
Constructors Constructor Description BoruvkaMST(EdgeWeightedGraph G)
Compute a minimum spanning tree (or forest) of an edgeweighted 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 theBoruvkaMST
data type.double
weight()
Returns the sum of the edge weights in a minimum spanning tree (or forest).



Constructor Detail

BoruvkaMST
public BoruvkaMST(EdgeWeightedGraph G)
Compute a minimum spanning tree (or forest) of an edgeweighted graph. Parameters:
G
 the edgeweighted 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 theBoruvkaMST
data type. Parameters:
args
 the commandline arguments

