Jarnik-Prim algorithm for finding the spanning tree of minimum weight of a weighted (connected) graph.
prim(
g,
d,
v = 1,
plot.steps = FALSE,
color = c("pink", "red", "gray50", "violet", "gray80"),
pause = 2,
pdf = FALSE,
...
)A list containing the minimum spanning tree in igraph format (components $tree and $arbol) and the corresponding minimum weight (components $weight and $peso).
A graph in igraph format.
A list of weights assigned to the edges of g in edgeid order.
Initial vertex to use in the first step of the algorithm. It defaults to 1.
Boolean indicating whether the routine should plot the intermediate steps of the algorithm to see the growing of the tree into the minimum spanning tree. It defaults to FALSE.
A set of colors to mark the vertices and edges added to the tree as it grows, and to visualize the cut of the added vertices set, see details below. It is only used when plot.steps is set to TRUE.
Time interval (in seconds) between successive steps of the algorithm. It is only used when plot.steps is set to TRUE and it defaults to 2.
Boolean indicating whether the routine should eject pdf plots of intermediate steps of the algorithm, see details below. It is only used when plot.steps is set to TRUE and it defaults to FALSE.
Further parameters to pass to the plotting routine, especially the layout parameter.
Cesar Asensio
The Jarnik-Prim algorithm in a weighted, connected graph of \(n\) vertices consists of growing an initially empty tree by adding to it the least weight edge in the cut set of the already added vertices, starting with a single vertex. Choosing each edge from this cutset guarantees that the added edges will form indeed a tree, that is, no cycle can be formed by this choice. The algorithm ends when the tree contains all \(n\) vertices.
This algorithm is exact, that is, it always finds a minimum solution. Please note that the minimum may not be unique, and different solutions with the same weight can be found by changing the initial vertex or the edge choice when some weights coincide.
This routine can plot the algorithm stepwise for illustrative purposes. To do that, set the parameter "plot.steps" to TRUE and adjust the "pause" parameter to some convenient value if desired (its default value is 2). The "color" parameter, a list of five R colors, is used to color the vertices and edges of the graph: The first color marks the vertices outside the growing tree and the second those inside it. The third color marks the edges incident to two vertices outside the tree, the fourth color marks the edges in the cut set of the added vertices and the fifth color marks the edges incident to two vertices inside the tree. The edges of the minimum weight spanning tree are colored with a fixed style and color. The default value of the "color" parameter is c("pink", "red", "gray50", "violet", "gray80"). Finally, by setting the "pdf" parameter to TRUE, this routine can also output the individual plots as a bunch of pdf files which can be included in a LaTeX animation.
library(igraph)
g <- make_graph("Frucht")
set.seed(1)
d <- round(runif(gsize(g), min = 1, max = 10)) # Random weights
T <- prim(g, d)
T$weight # = 47
## To plot the result:
## z <- layout_with_gem(g)
## T <- prim(g, d, plot.steps = TRUE, layout = z)
Run the code above in your browser using DataLab