Start with isolated vertices. In each round, determine the current connected components of a graph, choose a least-weight outgoing edge for each component, add their union, and recompute the components. With distinct weights, each chosen edge is the unique lightest edge across that component's graph cut. The minimum spanning tree cut property puts every such edge in every minimum spanning tree, so the selected edges remain acyclic. Every nonfinal component has an outgoing edge in a connected input, and merging makes progress until a spanning tree remains. Duplicate choices of the same edge are one set insertion.
Each new component contains at least two old components, so there are rounds. Scanning all edges per round gives time. Equal edge weights require a consistent secondary order to avoid choosing a cycle of tied edges.
Otakar Borůvka formulated the distinct-cost minimum-connection problem in 1926.[ref]
O jistém problému minimálním by Otakar Borůvka. pp. 37–38, opening formulation with positive distinct connection costs
Articles by others on the same topic
Borůvka's algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, weighted graph. Named after Czech mathematician Otakar Borůvka, the algorithm operates in the following manner: ### Steps of Borůvka's Algorithm: 1. **Initialization**: Start with each vertex in the graph as its own separate component (or tree).