Boruvka-Kruskal algorithm for finding the spanning tree of minimum weight of a weighted (connected) graph.
krus(
g,
d,
plot.steps = FALSE,
color = c("gray60", rainbow(12)),
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.
Boolean indicating whether the routine should plot the intermediate steps of the algorithm to see the growing of the forest into the minimum spanning tree. It defaults to FALSE.
A set of colors to see the different components of the forest as it grows, 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 Boruvka-Kruskal algorithm in a weighted, connected graph of \(n\) vertices consists of growing an initially empty forest by adding to it the least weight edge not yet added, while being careful to not close any cycles. The algorithm ends when the size of the forest is \(n-1\); then it becomes connected and, being acyclic, the forest is a tree.
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 edge ordering 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 R colors, is used to color the vertices of the graph: The first color marks the vertices outside the growing forest and the remaining colors are used for the different components of the forest, which coalesce in a single component (the minimum spanning tree) as the algorithm progresses. The default value of the "color" parameter is c("gray60", rainbow(12)), which might not be enough for large graphs. 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 <- krus(g, d)
T$weight # = 47
## To plot the result:
## z <- layout_with_gem(g)
## T <- krus(g, d, plot.steps = TRUE, layout = z)
Run the code above in your browser using DataLab