Borůvka's Algorithm

Boruvka's algorithm, published in 1926 and the oldest MST algorithm, finds a minimum spanning tree by letting every component simultaneously pick its cheapest outgoing edge. All selected edges are added at once, merging components in parallel rounds.

How it works

Each round scans all edges and records, for every component, the minimum-weight edge leaving it. Those edges are added to the forest, at least halving the number of components, so only O(log V) rounds are needed. Each round costs O(E), for a total of O(E log V). Because each round is a simple parallel scan, Boruvka is the natural basis for parallel and distributed MST computation.

Applications

Boruvka's algorithm was originally devised to plan an electrical network in Moravia and today underlies parallel MST implementations on GPUs and clusters, as well as hybrid algorithms that mix Boruvka rounds with Prim or Kruskal phases. It appears in interviews mainly as a discussion point on parallel algorithm design.