# minimum.spanning.tree

From igraph v0.1.2
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="unweighted", ...)`

##### Arguments

- graph
- The graph object to analyze.
- weights
- Numeric algorithm giving the weights of the edges in
the graph. The order should be the same as for given by
`get.edgelist`

. This is ignored for the`unweighted`

algorithm. - algorithm
- The algorithm to use for
calculation.
`unweighted`

can be used for unwieghted graphs, and`prim`

runs Prim's algorithm for weighted graphs. - ...
- 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`

.)

##### 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.1.2, License: GPL version 2 or later (June, 1991)*

### Community examples

Looks like there are no examples yet.