public class KruskalMST extends Object
KruskalMSTclass 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 Krusal's algorithm and the union-find data type. The constructor takes Θ(E log E) time in the worst case. Each instance method takes Θ(1) time. It uses Θ(E) extra space (not including the 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 KruskalMST(EdgeWeightedGraph G)
G- the edge-weighted graph
public double weight()
public static void main(String args)
args- the command-line arguments