Definitions

The minimum spanning tree (MST) of a set of n points is an acyclic undirected connected graph whose:

• vertices represent the points,

• edges are weighted by the distances between point pairs,

• edges have minimal total weight.

MSTs have many uses in, amongst others, topological data analysis (clustering, density estimation, dimensionality reduction, outlier detection, etc.).

The mst_euclid function can determine the classic Euclidean minimum spanning trees (EMST) as well as ones corresponding to mutual reachability distances [3].

Note

This section is a work in progress.

In the meantime, take a look at the Python or R package reference manual.

Relevant citations — the Jarnik-Prim algorithm: [6], [11], [12], the Boruvka algorithm: [2], [8], K-d trees: [1], [7], [13], mutual reachability distance: [3], [4].