# minspantree (biograph)

(To be removed) Find minimal spanning tree in biograph object

`minspantree (biograph)`

will be removed in a future release. Use the `minspantree`

function of `graph`

or `digraph`

instead.

## Syntax

`[`

* Tree*,

*] = minspantree(*

`pred`

*)*

`BGObj`

[

*,*

`Tree`

*] = minspantree(*

`pred`

*,*

`BGObj`

*)*

`R`

[

*,*

`Tree`

*] = minspantree(..., 'Method',*

`pred`

*, ...)*

`MethodValue`

[

*,*

`Tree`

*] = minspantree(..., 'Weights',*

`pred`

*, ...)*

`WeightsValue`

## Arguments

`BGObj` | Biograph object created by `biograph` (object
constructor). |

`R` | Scalar between 1 and the number of nodes. |

## Description

`[`

finds an acyclic subset of edges that connects all the nodes in the undirected graph
represented by an N-by-N adjacency matrix extracted from a biograph object,
* Tree*,

*] = minspantree(*

`pred`

*)*

`BGObj`

*, and for which the total weight is minimized. Weights of the edges are all nonzero entries in the lower triangle of the N-by-N sparse matrix. Output*

`BGObj`

*is a spanning tree represented by a sparse matrix. Output*

`Tree`

*is a vector containing the predecessor nodes of the minimal spanning tree (MST), with the root node indicated by*

`pred`

`0`

. The root node defaults to the first node in the largest
connected component. This computation requires an extra call to the
`graphconncomp`

function.**Note**

The function ignores the direction of the edges in the Biograph object.

`[`

sets the root of the minimal spanning tree to node * Tree*,

*] = minspantree(*

`pred`

*,*

`BGObj`

*)*

`R`

`R`

.`[`

calls * Tree*,

*] = minspantree(..., '*

`pred`

*',*

`PropertyName`

*, ...)*

`PropertyValue`

`minspantree`

with optional properties that use property
name/property value pairs. You can specify one or more properties in any order. Each
*must be enclosed in single quotes and is case insensitive. These property name/property value pairs are as follows:*

`PropertyName`

```
[
```

lets you specify the algorithm used to find the minimal spanning tree (MST). Choices
are:* Tree*,

*] = minspantree(..., 'Method',*

`pred`

*, ...)*

`MethodValue`

`'Kruskal'`

— Grows the minimal spanning tree (MST) one edge at a time by finding an edge that connects two trees in a spreading forest of growing MSTs. Time complexity is`O(E+X*log(N))`

, where`X`

is the number of edges no longer than the longest edge in the MST, and`N`

and`E`

are the number of nodes and edges respectively.`'Prim'`

— Default algorithm. Grows the minimal spanning tree (MST) one edge at a time by adding a minimal edge that connects a node in the growing MST with any other node. Time complexity is`O(E*log(N))`

, where`N`

and`E`

are the number of nodes and edges respectively.

**Note**

When the graph is unconnected, Prim's algorithm returns only the tree that contains R, while Kruskal's algorithm returns an MST for every component.

`[`

lets you specify custom weights for the edges. * Tree*,

*] = minspantree(..., 'Weights',*

`pred`

*, ...)*

`WeightsValue`

*is a column vector having one entry for every nonzero value (edge) in the N-by-N sparse matrix. The order of the custom weights in the vector must match the order of the nonzero values in the N-by-N sparse matrix when it is traversed column-wise. By default,*

`WeightsValue`

`minspantree`

gets weight information from the nonzero entries in
the N-by-N sparse matrix.## References

[1] Kruskal, J.B. (1956). On the Shortest Spanning Subtree
of a Graph and the Traveling Salesman Problem. Proceedings of the American
Mathematical Society *7*, 48-50.

[2] Prim, R. (1957). Shortest Connection Networks and Some
Generalizations. Bell System Technical Journal *36*,
1389-1401.

[3] Siek, J.G. Lee, L-Q, and Lumsdaine, A. (2002). The Boost Graph Library User Guide and Reference Manual, (Upper Saddle River, NJ:Pearson Education).

## Version History

**Introduced in R2006b**

## See Also

`minspantree`

| `graph`

| `digraph`