mst {igraph}

Minimum spanning tree

Description

A spanning tree of a connected graph is a connected subgraph with the smallest number of edges that includes all vertices of the graph. A graph will have many spanning trees. Among these, the minimum spanning tree will have the smallest sum of edge weights.

Usage

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

Arguments

graph

The graph object to analyze.

weights

Numeric vector 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 will 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 used.

...

Additional arguments, unused.

Details

The minimum spanning forest of a disconnected graph is the collection of minimum spanning trees of all of its components.

If the graph is not connected a minimum spanning forest is returned.

Value

A graph object with the minimum spanning forest. To check whether 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 [e-mail]

References

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

See Also

components()

Examples

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