igraph: mst – R documentation

Become an expert in R — Interactive courses, Cheat Sheets, certificates and more!

mst

Minimum spanning tree

Description

A subgraph of a connected graph is a minimum spanning tree if it is tree, and the sum of its edge weights are the minimal among all tree subgraphs of the graph. A minimum spanning forest of a graph is the graph consisting of the minimum spanning trees of its components.

Usage

mst(graph, weights = NULL, algorithm = NULL, ...)

Arguments

`graph`	The graph object to analyze.
`weights`	Numeric algorithm giving the weights of the edges in the graph. The order is determined by the edge ids. This is ignored if the `unweighted` algorithm is chosen. Edge weights are interpreted as distances.
`algorithm`	The algorithm to use for calculation. `unweighted` can be used for unweighted graphs, and `prim` runs Prim's algorithm for weighted graphs. If this is `NULL` then igraph tries to select the algorithm automatically: if the graph has an edge attribute called `weight` or the `weights` argument is not `NULL` then Prim's algorithm is chosen, otherwise the unweighted algorithm is performed.
`...`	Additional arguments, unused.

Details

If the graph is unconnected a minimum spanning forest is returned.

Value

A graph object with the minimum spanning forest. (To check that it is a tree check that the number of its edges is vcount(graph)-1.) The edge and vertex attributes of the original graph are preserved in the result.

Author(s)

Gabor Csardi csardi.gabor@gmail.com

References

Prim, R.C. 1957. Shortest connection networks and some generalizations Bell System Technical Journal, 37 1389–1401.

Examples

g <- sample_gnp(100, 3/100)
g_mst <- mst(g)

igraph

Network Analysis and Visualization

v1.2.10

GPL (>= 2)

Authors

See AUTHORS file.

Initial release

mst