Borůvka’s Algorithm

Background of minimum spanning tree

The oldest and arguably simplest minimum spanning tree algorithm was discovered by the Czech mathematician Otakar Borůvka in 1926, about a year after Jindřich Saxel asked him how to construct an electrical network connecting several cities using the least amount of wire. The algorithm was rediscovered by Gustav Choquet in 1938, rediscovered again by a team of Polish mathematicians led by Józef Łukaszewicz in 1951, and rediscovered again by George Sollin in 1961. Although Sollin never published his rediscovery, it was carefully described and credited in one of the first textbooks on graph algorithms; as a result, this algorithm is sometimes called “Sollin’s algorithm.”

Methodology

The Borůvka/Choquet/ Florek-Łukaziewicz-Perkal-Steinhaus-Zubrzycki / Prim / Sollin / Brosh algorithm can be summarized in one line:

$Borůvka$: Add all the safe edges and recurse.

Here is Borůvka’s algorithm in more detail. The algorithm calls the $Count AndLabel$ algorithm we studied before in this course to count the components of $F$ and label each vertex $v$ with an integer $comp(v)$ indicating its component.

$\underline{Borůvka(V, E):} \\ \hspace{0.4cm} F = (V, ∅) \\ \hspace{0.4cm} count ← CountAndLabel(F ) \\ \hspace{0.4cm} while\space count > 1 \\ \hspace{1cm} AddAllSafeEdges(E, F, count) \\ \hspace{1cm} count ← CountAndLabel(F ) \\ \hspace{0.4cm} return\space F$ ...