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
57
58
59
60
61
|
% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/minimum.spanning.tree.R
\name{mst}
\alias{mst}
\title{Minimum spanning tree}
\usage{
mst(graph, weights = NULL, algorithm = NULL, ...)
}
\arguments{
\item{graph}{The graph object to analyze.}
\item{weights}{Numeric vector 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. Edge weights are interpreted as
distances.}
\item{algorithm}{The algorithm to use for calculation. \code{unweighted} can
be used for unweighted graphs, and \code{prim} runs Prim's algorithm for
weighted graphs. If this is \code{NULL} then igraph will select the
algorithm automatically: if the graph has an edge attribute called
\code{weight} or the \code{weights} argument is not \code{NULL} then Prim's
algorithm is chosen, otherwise the unweighted algorithm is used.}
\item{\dots}{Additional arguments, unused.}
}
\value{
A graph object with the minimum spanning forest. To check whether 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 \emph{spanning tree} of a connected graph is a connected subgraph with
the smallest number of edges that includes all vertices of the graph.
A graph will have many spanning trees. Among these, the \emph{minimum spanning
tree} will have the smallest sum of edge weights.
}
\details{
The \emph{minimum spanning forest} of a disconnected graph is the collection
of minimum spanning trees of all of its components.
If the graph is not connected a minimum spanning forest is returned.
}
\examples{
g <- sample_gnp(100, 3 / 100)
g_mst <- mst(g)
}
\references{
Prim, R.C. 1957. Shortest connection networks and some
generalizations \emph{Bell System Technical Journal}, 37 1389--1401.
}
\seealso{
\code{\link[=components]{components()}}
}
\author{
Gabor Csardi \email{csardi.gabor@gmail.com}
}
\concept{minimum.spanning.tree}
\keyword{graphs}
|
