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.
minimum.spanning.tree(graph, weights=NULL, algorithm="unweighted", ...)
- The graph object to analyze.
- 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
- The algorithm to use for
unweightedcan be used for unwieghted graphs, and
primruns Prim's algorithm for weighted graphs.
- Additional arguments, unused.
If the graph is unconnected a minimum spanning forest is returned.
- A graph object with the minimum spanning forest. (To check that it is
a tree check that the number of its edges is
Prim, R.C. 1957. Shortest connection networks and some generalizations Bell System Technical Journal, 37 1389--1401.
g <- erdos.renyi.game(100, 3/100) mst <- minimum.spanning.tree(g)