Spanning trees
Graphs.jl contains a few algorithms to compute minimum spanning trees.
Index
Full docs
Graphs.boruvka_mst
— Functionboruvka_mst(g, distmx = weights(g); minimize = true)
Return a tuple (mst, weights)
where mst
is a vector of edges representing the optimum (minimum, by default) spanning tree of a connected, undirected graph g
with optional matrix distmx
that provides distinct edge weights, and weights
is the sum of all the edges in the solution by using Boruvka's algorithm. The algorithm requires that all edges have different weights to correctly generate a minimum/maximum spanning tree
Optional Arguments
minimize=true
: if set tofalse
, calculate the maximum spanning tree.
Graphs.kruskal_mst
— Functionkruskal_mst(g, distmx=weights(g); minimize=true)
Return a vector of edges representing the minimum (by default) spanning tree of a connected, undirected graph g
with optional distance matrix distmx
using Kruskal's algorithm.
Optional Arguments
minimize=true
: if set tofalse
, calculate the maximum spanning tree.
Graphs.prim_mst
— Functionprim_mst(g, distmx=weights(g))
Return a vector of edges representing the minimum spanning tree of a connected, undirected graph g
with optional distance matrix distmx
using Prim's algorithm. Return a vector of edges.