Algorithmus von Borůvka

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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

Literatur[Bearbeiten]

  • Borůvka, Otakar (1926). "O jistém problému minimálním (About a certain minimal problem)". Práce mor. přírodověd. spol. v Brně III (in Czech, German summary) 3: 37–58.
  • Borůvka, Otakar (1926). "Příspěvek k řešení otázky ekonomické stavby elektrovodních sítí (Contribution to the solution of a problem of economical construction of electrical networks)". Elektronický Obzor (in Czech) 15: 153–154.
  • Nešetřil, Jaroslav; Milková, Eva; Nešetřilová, Helena (2001). "Otakar Borůvka on minimum spanning tree problem: translation of both the 1926 papers, comments, history". Discrete Mathematics 233 (1–3): 3–36. doi:10.1016/S0012-365X(00)00224-7.
  • Choquet, Gustave (1938). "Étude de certains réseaux de routes". Comptes-rendus de l’Académie des Sciences (in French) 206: 310–313.
  • Florek, Kazimierz (1951). "Sur la liaison et la division des points d'un ensemble fini". Colloquium Mathematicum 2 (1951) (in French): 282–285.
  • Sollin, M. (1965). "Le tracé de canalisation". Programming, Games, and Transportation Networks (in French).
  • Eppstein, David (1999). "Spanning trees and spanners". In Sack, J.-R.; Urrutia, J. Handbook of Computational Geometry. Elsevier. pp. 425–461.
  • Mareš, Martin (2004). "Two linear time algorithms for MST on minor closed graph classes". Archivum mathematicum 40 (3): 315–320.