Minimum spanning trees and clusters

The Euclidean minimum spanning tree for a set of points is the shortest tree connecting all the points. It can be used for clustering, by dropping the longest edges. There are three related greedy algorithms for the minimum spanning tree, all of which come very close to the lower bound for asymptotic complexity. Kruskal’s algorithm (also known as ‘single linkage clustering’) adds the shortest edge that does not form a cycle, and ends up with a tree only at the last step. Prim’s algorithm maintains a tree at all times, adding the shortest edge that connects a point in the tree to a point outside the tree. Boruvka’s algorithm maintains a forest that is reduced at each step by connecting each tree to its closest neighbour. Kruskal’s algorithm is efficient for sparse graphs but requires O(n2) space for a Euclidean spanning tree on n points. Boruvka’s algorithm is attractive largely because it can be run in parallel very efficiently. Prim’s algorithm is easiest to implement for large Euclidean minimum spanning trees.