# graphminspantree

(To be removed) Find minimal spanning tree in graph

`graphminspantree` will be removed in a future release. Use `minspantree` instead. For details, see Compatibility Considerations.

## Syntax

```[Tree, pred] = graphminspantree(G) [Tree, pred] = graphminspantree(G, R) [Tree, pred] = graphminspantree(..., 'Method', MethodValue, ...) [Tree, pred] = graphminspantree(..., 'Weights', WeightsValue, ...) ```

## Arguments

 `G` N-by-N adjacency matrix that represents an undirected graph. Nonzero entries in matrix `G` represent the weights of the edges. `R` Scalar between 1 and the number of nodes.

## Description

Tip

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

```[Tree, pred] = graphminspantree(G)``` finds an acyclic subset of edges that connects all the nodes in the undirected graph `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 `Tree` is a spanning tree represented by an adjacency matrix. Output `pred` is a vector containing the predecessor nodes of the minimal spanning tree (MST), with the root node indicated by `0`. The root node defaults to the first node in the largest connected component. This computation requires an extra call to the `graphconncomp` function.

```[Tree, pred] = graphminspantree(G, R)``` sets the root of the minimal spanning tree to node `R`.

```[Tree, pred] = graphminspantree(..., 'PropertyName', PropertyValue, ...)``` calls `graphminspantree` with optional properties that use property name/property value pairs. You can specify one or more properties in any order. Each `PropertyName` must be enclosed in single quotes and is case insensitive. These property name/property value pairs are as follows:

``` [Tree, pred] = graphminspantree(..., 'Method', MethodValue, ...)``` lets you specify the algorithm used to find the minimal spanning tree (MST). Choices are:

• `'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.

```[Tree, pred] = graphminspantree(..., 'Weights', WeightsValue, ...)``` lets you specify custom weights for the edges. `WeightsValue` is a column vector having one entry for every nonzero value (edge) in matrix `G`. 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, `graphminspantree` gets weight information from the nonzero entries in matrix `G`.

## References

 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.

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

 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

expand all

Warns starting in R2022a

Behavior changed in R2021b