minimum.spanning.tree {igraph} | R Documentation

## 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

    minimum.spanning.tree(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

`algorithm`

The algorithm to use for calculation. `unweighted` can be used for unwieghted 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` of the `weights` argument is not `NULL` then Prim's algorithm is chosen, otherwise the unwweighted 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@rmki.kfki.hu

### References

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

### See Also

`clusters`

### Examples

    g <- erdos.renyi.game(100, 3/100)
    mst <- minimum.spanning.tree(g)

[Package igraph version 0.5.2 Index]