minimum.spanning.tree {igraph} | R Documentation |
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=NULL, ...)
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 |
algorithm |
The algorithm to use for
calculation. |
... |
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 vcount(graph)-1
.)
The edge and vertex attributes of the original graph are preserved in
the result.
Gabor Csardi csardi@rmki.kfki.hu
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)