minimum.spanning.tree

0th

Percentile

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

clusters

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