public class BoruvkaMST extends Object
This implementation uses Boruvka's algorithm and the union-find data type. The constructor takes time proportional to E log V and extra space (not including the graph) proportional to V, where V is the number of vertices and E is the number of edges. Afterwards, the weight() method takes constant time and the edges() method takes time proportional to V.
For additional documentation, see Section 4.4 of
Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
For alternate implementations, see LazyPrimMST, PrimMST,
and KruskalMST.
| Constructor and Description |
|---|
BoruvkaMST(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 BoruvkaMST data type.
|
double |
weight()
Returns the sum of the edge weights in a minimum spanning tree (or forest).
|
public BoruvkaMST(EdgeWeightedGraph G)
G - the edge-weighted graphpublic Iterable<Edge> edges()
public double weight()
public static void main(String[] args)
Copyright © 2014. All Rights Reserved.