Algorithmus von Borůvka

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Die fraglichen Angaben werden daher möglicherweise demnächst entfernt. Bitte hilf der Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst. Näheres ist eventuell auf der Diskussionsseite oder in der Versionsgeschichte angegeben. Bitte entferne zuletzt diese Warnmarkierung.

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[Bearbeiten]

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|).