Search this API

## y.algo Class SpanningTrees

```java.lang.Object
y.algo.SpanningTrees
```

`public class SpanningTreesextends java.lang.Object`

This class provides (minimum) spanning tree algorithms for graphs.

### Definitions

• A spanning tree of an undirected connected graph is a subset of its edges that induce a tree that connects all nodes of the graph.
• A minimum spanning tree of a weighted connected graph is a spanning tree whose edges have minimum overall cost among all spanning trees of that graph.

Method Summary
`static double` ```cost(EdgeList treeEdges, DataProvider edgeCost)```
Returns the overall cost of a previously calculated minimum spanning tree.
`static EdgeList` ```kruskal(Graph graph, DataProvider cost)```
Calculates a minimum spanning tree for the given graph.
`static EdgeList` ```minimum(Graph graph, DataProvider cost)```
Calculates a minimum spanning tree for the given graph.
`static EdgeList` ```prim(Graph graph, DataProvider cost)```
Calculates a minimum spanning tree for the given graph.
`static EdgeList` `uniform(Graph graph)`
Calculates a spanning tree for the given graph in which each edge has a uniform cost of `1.0`.

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Method Detail

### minimum

```public static EdgeList minimum(Graph graph,
DataProvider cost)```
Calculates a minimum spanning tree for the given graph.

Currently, the result is obtained by calling `prim(Graph, DataProvider)`.

Preconditions:
The graph must be `connected`.
`cost.length == graph.E()`
Complexity:
`graph.E() * log(graph.N())`
Parameters:
`graph` - the input graph
`cost` - the `DataProvider` that returns a double value (cost) for each edge
Returns:
a `list` containing the edges that form the minimum spanning tree

### kruskal

```public static EdgeList kruskal(Graph graph,
DataProvider cost)```
Calculates a minimum spanning tree for the given graph.

The implementation is based on an algorithm originally published in:

• J.B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, pages 48-50, 1956.

Preconditions:
The graph must be `connected`.
`cost.length == graph.E()`
Complexity:
`graph.E() + graph.N() * log(graph.N())`
Parameters:
`graph` - the input graph
`cost` - the `DataProvider` that returns a double value (cost) for each edge
Returns:
a `list` containing the edges that form the minimum spanning tree

### prim

```public static EdgeList prim(Graph graph,
DataProvider cost)```
Calculates a minimum spanning tree for the given graph.

The implementation is based on an algorithm originally published in:

• R.C. Prim. Shortest connection networks and some generalizations. Bell System Technical Journal, 36:1389-1401, 1957.

Preconditions:
The graph must be `connected`.
`cost.length == graph.E()`
Complexity:
`graph.E() * log(graph.N())`
Parameters:
`graph` - the input graph
`cost` - the `DataProvider` that returns a double value (cost) for each edge
Returns:
a `list` containing the edges that form the minimum spanning tree

### uniform

`public static EdgeList uniform(Graph graph)`
Calculates a spanning tree for the given graph in which each edge has a uniform cost of `1.0`.

Precondition:
The graph must be `connected`.
Complexity:
`O(graph.E() + graph.N())`
Parameters:
`graph` - the input graph
Returns:
a `list` containing the edges that form the minimum spanning tree

### cost

```public static double cost(EdgeList treeEdges,
DataProvider edgeCost)```
Returns the overall cost of a previously calculated minimum spanning tree.

Parameters:
`treeEdges` - the given `list` of edges that form a minimum spanning tree
`edgeCost` - the `DataProvider` that returns a double value (cost) for each tree edge
Returns:
the overall cost of the tree edges