# minimum.spanning.tree

From igraph v0.4.4
by Gabor Csardi

##### Minimum spanning tree

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.

- Keywords
- graphs

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

##### References

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

##### See Also

##### Examples

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

*Documentation reproduced from package igraph, version 0.4.4, License: GPL version 2 or later (June, 1991)*

### Community examples

Looks like there are no examples yet.