Main Content

Find minimal spanning tree in graph

`[`

* Tree*,

`pred`

`G`

[

`Tree`

`pred`

`G`

`R`

[

`Tree`

`pred`

`MethodValue`

[

`Tree`

`pred`

`WeightsValue`

`G` | N-by-N sparse 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. |

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

`pred`

`G`

`G`

`G`

`Tree`

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

`pred`

`G`

`R`

`R`

.`[`

calls * Tree*,

`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 `PropertyName`

```
[
```

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

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

`pred`

`WeightsValue`

`WeightsValue`

`G`

`G`

`graphminspantree`

gets
weight information from the nonzero entries in matrix `G`

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'))

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'))

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

`graphallshortestpaths`

| `graphconncomp`

| `graphisdag`

| `graphisomorphism`

| `graphisspantree`

| `graphmaxflow`

| `graphpred2path`

| `graphshortestpath`

| `graphtopoorder`

| `graphtraverse`

| `minspantree`