graphminspantree
(Removed) Find minimal spanning tree in graph
graphminspantree
has been removed. Use minspantree
instead. For details, see Version History.
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 adjacency 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.
[
finds an acyclic subset of edges that connects all the nodes in the undirected graph
Tree
, pred
]
= graphminspantree(G
)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 adjacency matrix
G
. Output Tree
is a spanning
tree represented by an adjacency 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.
[
sets the root of the minimal spanning tree to node Tree
, pred
]
= graphminspantree(G
, R
)R
.
[
calls Tree
,
pred
] = graphminspantree(..., '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
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
]
= graphminspantree(..., '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 isO(E+X*log(N))
, whereX
is the number of edges no longer than the longest edge in the MST, andN
andE
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 isO(E*log(N))
, whereN
andE
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
]
= graphminspantree(..., 'Weights', WeightsValue
, ...)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
.
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).