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


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Algorithmus von Borůvka — 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 …   Deutsch Wikipedia

  • Algorithmus von Dijkstra — Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) dient der Berechnung eines kürzesten Pfades zwischen einem Startknoten und einem beliebigen Knoten in einem kantengewichteten Graphen. Die Gewichte dürfen dabei nicht negativ… …   Deutsch Wikipedia

  • Boruvka — Otakar Borůvka (* 10. Mai 1899 in Uherský Ostroh, Mähren; † 22. Juli 1995 in Brno, Tschechien) war ein tschechischer Mathematiker, der heute vor allem durch seine Beiträge zur Graphentheorie bekannt ist, die er schon lange vor der Etablierung der …   Deutsch Wikipedia

  • Borůvka — Otakar Borůvka (* 10. Mai 1899 in Uherský Ostroh, Mähren; † 22. Juli 1995 in Brno, Tschechien) war ein tschechischer Mathematiker, der heute vor allem durch seine Beiträge zur Graphentheorie bekannt ist, die er schon lange vor der Etablierung der …   Deutsch Wikipedia

  • Otakar Borůvka — (* 10. Mai 1899 in Uherský Ostroh, Mähren; † 22. Juli 1995 in Brno, Tschechien) war ein tschechischer Mathematiker, der heute vor allem durch seine Beiträge zur Graphentheorie bekannt ist, die er schon lange vor der Etablierung der Graphentheorie …   Deutsch Wikipedia

  • Dijkstras Algorithmus — Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) dient der Berechnung eines kürzesten Pfades zwischen einem Startknoten und einem beliebigen Knoten in einem kantengewichteten Graphen. Die Gewichte dürfen dabei nicht negativ… …   Deutsch Wikipedia

  • Dijkstra-Algorithmus — Animation des Dijkstra Algorithmus Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) ist ein Algorithmus aus der Klasse der Greedy Algorithmen und löst das Problem der kürzesten Pfade für einen gegebenen Startknoten. Er… …   Deutsch Wikipedia

  • Liste von Algorithmen — Dies ist eine Liste von Artikeln zu Algorithmen in der deutschsprachigen Wikipedia. Siehe auch unter Datenstruktur für eine Liste von Datenstrukturen. Inhaltsverzeichnis 1 Klassen von Algorithmen nach Komplexität 2 Klassen von Algorithmen nach… …   Deutsch Wikipedia

  • Spannbaum-Algorithmus — Ein Graph mit einem minimalen Spannbaum. Ein Spannbaum (auch aufspannender Baum oder manchmal spannender Baum genannt; englisch spanning tree) ist in der Graphentheorie ein Teilgraph eines ungerichteten Graphen, der ein Baum ist und alle Knoten… …   Deutsch Wikipedia

  • Dijkstraalgorithmus — Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) dient der Berechnung eines kürzesten Pfades zwischen einem Startknoten und einem beliebigen Knoten in einem kantengewichteten Graphen. Die Gewichte dürfen dabei nicht negativ… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”