Spanning trees

Graphs.jl contains a few algorithms to compute minimum spanning trees.

Index

Full docs

Graphs.boruvka_mstFunction
boruvka_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 to false, calculate the maximum spanning tree.
source
Graphs.kruskal_mstFunction
kruskal_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 to false, calculate the maximum spanning tree.
source
Graphs.prim_mstFunction
prim_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.

source