\HeaderA{minimum.spanning.tree}{Minimum spanning tree}{minimum.spanning.tree}
\keyword{graphs}{minimum.spanning.tree}
\begin{Description}\relax
A subgraph of a connected graph is a \emph{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.
\end{Description}
\begin{Usage}
\begin{verbatim}
minimum.spanning.tree(graph, weights=NULL, algorithm=NULL, ...)
\end{verbatim}
\end{Usage}
\begin{Arguments}
\begin{ldescription}
\item[\code{graph}] The graph object to analyze.
\item[\code{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 \code{unweighted} algorithm is chosen

\item[\code{algorithm}] The algorithm to use for
calculation. \code{unweighted} can be used for unwieghted graphs,
and \code{prim} runs Prim's algorithm for weighted graphs.
If this is \code{NULL} then igraph tries to select the algorithm
automatically: if the graph has an edge attribute called
\code{weight} of the \code{weights} argument is not \code{NULL} then
Prim's algorithm is chosen, otherwise the unwweighted algorithm is
performed.

\item[\code{...}] Additional arguments, unused.
\end{ldescription}
\end{Arguments}
\begin{Details}\relax
If the graph is unconnected a minimum spanning forest is returned.
\end{Details}
\begin{Value}
A graph object with the minimum spanning forest. (To check that it is
a tree check that the number of its edges is \code{vcount(graph)-1}.)
The edge and vertex attributes of the original graph are preserved in
the result.
\end{Value}
\begin{Author}\relax
Gabor Csardi \email{csardi@rmki.kfki.hu}
\end{Author}
\begin{References}\relax
Prim, R.C. 1957. Shortest connection networks and some
generalizations \emph{Bell System Technical Journal}, 37 1389--1401.
\end{References}
\begin{SeeAlso}\relax
\code{\LinkA{clusters}{clusters}}
\end{SeeAlso}
\begin{Examples}
\begin{ExampleCode}
g <- erdos.renyi.game(100, 3/100)
mst <- minimum.spanning.tree(g)
\end{ExampleCode}
\end{Examples}

