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="unweighted", ...)
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. |
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
.)
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)