# Documentation

### This is machine translation

Translated by
Mouseover text to see original. Click the button below to return to the English version of the page.

# graphminspantree

Find minimal spanning tree in graph

## 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 sparse 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 sparse matrix `G`. Output `Tree` is a spanning tree represented by a sparse 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`.

## Examples

1. Create and view an undirected graph with 6 nodes and 11 edges.

```W = [.41 .29 .51 .32 .50 .45 .38 .32 .36 .29 .21]; DG = sparse([1 1 2 2 3 4 4 5 5 6 6],[2 6 3 5 4 1 6 3 4 2 5],W); UG = tril(DG + DG') UG = (2,1) 0.4100 (4,1) 0.4500 (6,1) 0.2900 (3,2) 0.5100 (5,2) 0.3200 (6,2) 0.2900 (4,3) 0.5000 (5,3) 0.3200 (5,4) 0.3600 (6,4) 0.3800 (6,5) 0.2100 view(biograph(UG,[],'ShowArrows','off','ShowWeights','on'))```

2. Find and view the minimal spanning tree of the undirected graph.

``` [ST,pred] = graphminspantree(UG) ST = (6,1) 0.2900 (6,2) 0.2900 (5,3) 0.3200 (5,4) 0.3600 (6,5) 0.2100 pred = 0 6 5 5 6 1 view(biograph(ST,[],'ShowArrows','off','ShowWeights','on'))```

## 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).

Get trial now