Borůvka's algorithm
algorithm for finding minimum spanning trees by repeatedly finding the shortest edge out of each subtree in a forest and adding all such edges to the forest
Borůvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a graph,
or a minimum spanning forest in the case of a graph that is not connected.
It was first published in 1926 by Otakar Borůvka as a method of constructing an efficient electricity network for Moravia.
The algorithm was rediscovered by Choquet in 1938; again by Florek, Łukasiewicz, Perkal, Steinhaus, and Zubrzycki in 1951; and again by Georges Sollin in 1965. This algorithm is frequently called Sollin's algorithm, especially in the parallel computing literature.
The algorithm begins by finding the minimum-weight edge incident to each vertex of the graph, and adding all of those edges to the forest.
Then, it repeats a similar process of finding the minimum-weight edge from each tree constructed so far to a different tree, and adding all of those edges to the forest.
Each repetition of this process reduces the number of trees, within each connected component of the graph, to at most half of this former value,
so after logarithmically many repetitions the process finishes. When it does, the set of edges it has added forms the minimum spanning forest.
Pseudocode
The following pseudocode illustrates a basic implementation of Borůvka's algorithm.
In the conditional clauses, every edge uv is considered cheaper than "None".
The public source identifies “Borůvka's algorithm” as algorithm for finding minimum spanning trees by repeatedly finding the shortest edge out of each subtree in a forest and adding all such edges to the forest. This brief keeps that definition visible, then builds a research path around Borůvka's, algorithm and finding.
Why this record matters
A short description can identify a subject without explaining its stakes. For “Borůvka's algorithm”, the useful work is to connect “algorithm for finding minimum spanning trees by repeatedly finding the shortest edge out of each subtree in a forest and adding all such edges to the forest” to the records capable of establishing context and consequence.
The citation trail is more important than the brevity of the summary: it shows where individual claims can be examined in context. The source revision retrieved here is dated Aug 14, 2026. The linked authority identifier is Q1468211. None of the 1 selected statements returned an explicit reference. The first chronological checks are 1926, 1938, 1951 and 1965.
The absence of detail may reflect summary conventions rather than a lack of surviving documentation. The lead is largely declarative, so disagreement and counter-evidence require a deliberate search beyond the opening account. Authority statements aid reconciliation but still require their own references, qualifiers and ranks to be checked.
How to read it
Use the entry as an orientation point, then follow its citations and revision history. Names, dates and institutional relationships should be checked against the original record.
- Subject orientation
- Search vocabulary
- Locating named sources
The closest primary source, responsible institution and strongest cited specialist reference.
Three-step research path
- Establish the record: confirm the title “Borůvka's algorithm”, its source revision and the description used here.
- Expand the search: follow Borůvka's algorithm primary sources, Borůvka's algorithm archive and Borůvka's research across catalogues and specialist indexes.
- Test the account: compare the strongest cited source with the responsible institution’s current record and note any disagreement.
Questions for further research
- Which source most directly establishes the central claim about “Borůvka's algorithm”?
- What terminology or title could unlock a more precise catalogue search?
- Which institution is responsible for the underlying evidence?
Search terms from this dossier
This entry incorporates text from “Borůvka's algorithm” on English Wikipedia. Contributors are listed in the page history. Text is available under the Creative Commons Attribution-ShareAlike 4.0 License. Selected authority identifiers and statements are retrieved from Wikidata under CC0; their references and qualifiers remain part of the verification path.