Algorithms For Dummies

 

»

Borůvka’s: Invented by Otakar Borůvka in 1926 to solve the problem of 

finding the optimal way to supply electricity in Moravia. The algorithm relies 

on a series of stages in which it identifies the edges with the smallest weight in 

each stage. The calculations begin by looking at individual vertexes, finding 

the smallest weight for that vertex, and then combining paths to form forests 

of individual trees until it creates a path that combines all the forests with the 

smallest weight.

 

»

Prim’s: Originally invented by Jarnik in 1930, Prim rediscovered it in 1957. This 

algorithm starts with an arbitrary vertex and grows the minimum spanning 

tree one edge at a time by always choosing the edge with the least weight.

 

»

Kruskal’s: Developed by Joseph Kruskal in 1956, it uses an approach that 

combines Borůvka’s algorithm (creating forests of individual trees) and Prim’s 

algorithm (looking for the minimum edge for each vertex and building the 

forests one edge at a time).