1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
% Generated by roxygen2 (4.1.1): do not edit by hand
% Please edit documentation in R/minimum.spanning.tree.R
\name{mst}
\alias{minimum.spanning.tree}
\alias{mst}
\title{Minimum spanning tree}
\usage{
mst(graph, weights = NULL, algorithm = NULL, ...)
}
\arguments{
\item{graph}{The graph object to analyze.}
\item{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{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{\dots}{Additional arguments, unused.}
}
\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.
}
\description{
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.
}
\details{
If the graph is unconnected a minimum spanning forest is returned.
}
\examples{
g <- sample_gnp(100, 3/100)
g_mst <- mst(g)
}
\author{
Gabor Csardi \email{csardi.gabor@gmail.com}
}
\references{
Prim, R.C. 1957. Shortest connection networks and some
generalizations \emph{Bell System Technical Journal}, 37 1389--1401.
}
\seealso{
\code{\link{components}}
}
\keyword{graphs}
|
