public class BoruvkaMST extends Object
BoruvkaMSTclass 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).
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.
|Constructor and Description|
Compute a minimum spanning tree (or forest) of an edge-weighted graph.
|Modifier and Type||Method and Description|
Returns the edges in a minimum spanning tree (or forest).
Unit tests the
Returns the sum of the edge weights in a minimum spanning tree (or forest).
public BoruvkaMST(EdgeWeightedGraph G)
G- the edge-weighted graph
public double weight()
public static void main(String args)
args- the command-line arguments