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 unweighted algorithm is chosen
|
algorithm |
The algorithm to use for
calculation. unweighted can be used for unwieghted graphs,
and prim runs Prim's algorithm for weighted graphs.
If this is NULL then igraph tries to select the algorithm
automatically: if the graph has an edge attribute called
weight of the weights argument is not NULL then
Prim's algorithm is chosen, otherwise the unwweighted algorithm is
performed.
|
... |
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)