Graph algorithms / interactive lesson
Build a minimum spanning tree by letting every component choose its cheapest outgoing edge in parallel. Watch proposals, deduplication, merges, and cycle rejections round by round.
About the algorithm
Boruvka's algorithm constructs a minimum spanning tree by repeatedly letting every connected component choose its cheapest outgoing edge. Unlike Prim's single growing tree, Boruvka grows many trees at once and merges them round by round.
Otakar Boruvka published the algorithm in 1926 while studying how to build an efficient electrical power network in Moravia. It is one of the oldest known minimum spanning tree algorithms and predates the widely taught Prim and Kruskal algorithms.
Start with every vertex as a separate component. In each round, every component scans edges that leave it and proposes the cheapest one. The unique proposed edges are processed: if an edge connects two different components, add it to the forest and merge those components; if both endpoints are already in the same component, reject it to avoid a cycle. Repeat until only one component remains.
Boruvka's algorithm is useful for parallel and distributed MST construction because many components can search independently. It also appears inside hybrid MST algorithms and graph processing systems where reducing the number of components quickly is valuable.
Code companion
Connect each visual decision to an implementation pattern.
components = one component per vertex
mst = []
while there is more than one component:
proposals = []
for each component C:
edge = cheapest edge leaving C
proposals.add(edge)
for each unique edge in proposals:
if edge connects two different components:
mst.add(edge)
merge the two components
return mst