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

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

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

Find minimal spanning tree in biograph object

`[`

* Tree*,

`pred`

`BGObj`

[

`Tree`

`pred`

`BGObj`

`R`

[

`Tree`

`pred`

`MethodValue`

[

`Tree`

`pred`

`WeightsValue`

`BGObj` | Biograph object created by `biograph` (object
constructor). |

`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 represented by an N-by-N adjacency matrix extracted from a biograph
object, * Tree*,

`pred`

`BGObj`

`BGObj`

`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.The function ignores the direction of the edges in the Biograph object.

`[`

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

`pred`

`BGObj`

`R`

`R`

.`[`

calls * Tree*,

`pred`

`PropertyName`

`PropertyValue`

`minspantree`

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`

`minspantree`

gets
weight information from the nonzero entries in the N-by-N sparse matrix.[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).

`allshortestpaths`

| `biograph`

| `conncomp`

| `graphminspantree`

| `isdag`

| `isomorphism`

| `isspantree`

| `maxflow`

| `shortestpath`

| `topoorder`

| `traverse`

Was this topic helpful?