# graphminspantree

(Removed) Find minimal spanning tree in graph

`graphminspantree`

has been removed. Use `minspantree`

instead. For details, see Version History.

## Syntax

`[`

* Tree*,

*] = graphminspantree(*

`pred`

*)*

`G`

[

*,*

`Tree`

*] = graphminspantree(*

`pred`

*,*

`G`

*)*

`R`

[

*,*

`Tree`

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

`pred`

*, ...)*

`MethodValue`

[

*,*

`Tree`

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

`pred`

*, ...)*

`WeightsValue`

## Arguments

`G` | N-by-N adjacency matrix that represents an undirected graph.
Nonzero entries in matrix represent the
weights of the edges.`G` |

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

## Description

**Tip**

For introductory information on graph theory functions, see Graph Theory Functions.

`[`

finds an acyclic subset of edges that connects all the nodes in the undirected graph
* Tree*,

*] = graphminspantree(*

`pred`

*)*

`G`

*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 adjacency matrix*

`G`

*. Output*

`G`

*is a spanning tree represented by an adjacency 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.`[`

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

*] = graphminspantree(*

`pred`

*,*

`G`

*)*

`R`

`R`

.`[`

calls * Tree*,

*] = graphminspantree(..., '*

`pred`

*',*

`PropertyName`

*, ...)*

`PropertyValue`

`graphminspantree`

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*,

*] = graphminspantree(..., '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*,

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

`pred`

*, ...)*

`WeightsValue`

*is a column vector having one entry for every nonzero value (edge) in matrix*

`WeightsValue`

*. The order of the custom weights in the vector must match the order of the nonzero values in matrix*

`G`

*when it is traversed column-wise. By default,*

`G`

`graphminspantree`

gets weight
information from the nonzero entries in matrix *.*

`G`

## 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**