Bioinformatics Toolbox™

graphminspantree - Find minimal spanning tree in graph

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 sparse 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 in the Bioinformatics Toolbox™ User's Guide.

[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 sparse matrix G. 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.

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

Examples

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'))

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.