Algorithmus von Boruvka

Der Algorithmus von Borůvka gilt als erster Algorithmus zum Auffinden minimaler Spannbäume in ungerichteten Graphen. Er wurde 1926 von dem tschechischen Mathematiker Otakar Borůvka beschrieben. Die beiden bekannteren Algorithmen zur Lösung dieses Problems sind der Algorithmus von Prim und der Algorithmus von Kruskal. In der Erstveröffentlichung dieser beiden Algorithmen wird Borůvka jeweils erwähnt.

Grundprinzip und Komplexität

Wie auch der Algorithmus von Kruskal startet der Algorithmus von Borůvka mit vielen Teilgerüsten, die aus jeweils einem Knoten der Knotenmenge V des Graphen G = (V, E) bestehen. In jeder nun folgenden Iteration wird eine kürzeste Kante von einem Teilgerüst zu einem anderen gesucht. Die Auswahl dieser Kanten kann insbesondere bei der Möglichkeit zur parallelen Ausführung simultan geschehen, was den Algorithmus attraktiv für parallele Implementierungen macht. Die so verbundenen Teilgerüste werden zu jeweils einem Teilgerüst verschmolzen. Bei jeder Iteration halbiert sich auf diese Weise die Zahl der Teilgerüste, so dass der Algorithmus in maximal log n Phasen terminiert. Da zur Auswahl der jeweils kürzesten Kante zuvor ein Sortierverfahren angewendet werden muss, dominiert also die Komplexität des Sortierens den Algorithmus. Diese liegt bei O(|E| log |V|).