Find minimal spanning tree in biograph object
[
Tree
, pred
]
= minspantree(BGObj
)
[Tree
, pred
]
= minspantree(BGObj
, R
)[
Tree
, pred
]
= minspantree(..., 'Method', MethodValue
, ...)[
Tree
, pred
]
= minspantree(..., 'Weights', WeightsValue
, ...)
BGObj | Biograph object created by biograph (object
constructor). |
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 represented by an N-by-N adjacency matrix extracted from a biograph
object, Tree
, pred
]
= minspantree(BGObj
)BGObj
, 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. 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.
Note: The function ignores the direction of the edges in the Biograph object. |
[
sets
the root of the minimal spanning tree to node Tree
, pred
]
= minspantree(BGObj
, R
)R
.
[
calls Tree
, pred
]
= minspantree(..., '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
must
be enclosed in single quotes and is case insensitive. These property
name/property value pairs are as follows:
lets you specify the algorithm
used to find the minimal spanning tree (MST). Choices are:[
Tree
, pred
]
= minspantree(..., 'Method', 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
]
= minspantree(..., 'Weights', WeightsValue
, ...)WeightsValue
is a column
vector having one entry for every nonzero value (edge) in the N-by-N
sparse matrix. The order of the custom weights in the vector must
match the order of the nonzero values in the N-by-N sparse matrix
when it is traversed column-wise. By default, 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