The minimum spanning tree problem originated in the 1920s when O. Borůvka
identified and solved the problem during the electrification of Moravia. This graph
theory problem and its numerous applications have inspired many others to
look for alternate ways of finding a spanning tree of minimum weight in a
weighted, connected graph since Borůvka’s time. This note presents a variant of
Borůvka’s algorithm that developed during the graph theory course work of
undergraduate students. We discuss the proof of the algorithm, compare it
to existing algorithms, and present an implementation of the procedure in
Maple.
Keywords
minimum spanning tree, graph algorithm, graph theory, Maple