Main Content

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.
RScalar between 1 and the number of nodes.

Description

Tip

For introductory information on graph theory functions, see Graph Theory Functions.

[Tree, pred] = graphminspantree(G) finds an acyclic subset of edges that connects all the nodes in the undirected graph 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.

[Tree, pred] = graphminspantree(G, R) sets the root of the minimal spanning tree to node R.

[Tree, pred] = graphminspantree(..., 'PropertyName', PropertyValue, ...) calls 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:

[Tree, pred] = graphminspantree(..., 'Method', MethodValue, ...) lets you specify the algorithm used to find the minimal spanning tree (MST). Choices are:

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

[Tree, pred] = graphminspantree(..., 'Weights', WeightsValue, ...) lets you specify custom weights for the edges. 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).

Version History

Introduced in R2006b

expand all

R2022b: Removed

graphminspantree has been removed. Use minspantree instead. When you run minspantree by setting the 'Type' name-value argument to 'forest', the returned list of predecessors includes predecessor node IDs even though they are not reachable from the original root. graphminspantree sets the predecessors for those unreachable nodes from the root to be NaN.

See Also