Note: This page has been translated by MathWorks. Please click here

To view all translated materials including this page, select Japan from the country navigator on the bottom of this page.

To view all translated materials including this page, select Japan from the country navigator on the bottom of this page.

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

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.

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`

Was this topic helpful?