Boruvka Algorithm

overview

Summary

Boruvka's algorithm builds a minimum spanning tree by repeatedly connecting each component to its cheapest outgoing edge. It starts with every vertex as its own component and merges components in rounds until only one remains. The method is highly parallelizable, works with negative weights, and produces a minimum spanning forest if the graph is disconnected. Its typical time complexity is O(E log V) with a union-find data structure.