Borůvka-Algorithmus: Unterschied zwischen den Versionen

Version vom 31. März 2023, 07:10 Uhr

Ein Beispielgraph

Der Borůvka-Algorithmus ist ein Algorithmus, der zu einem gegebenen gewichteten Graphen einen minimalen Spannbaum erzeugt.

Der Algorithmus wurde 1926 von Otakar Borůvka entworfen und arbeitet wie folgt:

Gegeben sei ein Graph G.
Erzeuge einen neuen Graphen T, der später der gesuchte Spannbaum wird.
Füge alle Knoten, aber keine Kanten des Graphen G zu T hinzu.
Wiederhole die folgenden Schritte, bis T zusammenhängend ist:
1. Füge zu jeder Zusammenhangskomponente von T deren kleinste ausgehende Kante in G hinzu.

So erzeugt der Borůvka-Algorithmus aus dem Beispielgraphen einen MST:

Da $T$ nun zusammenhängend ist, terminiert der Algorithmus.

@@ Zeile 83: / Zeile 83: @@
 linkStyle 5 stroke:purple, stroke-width: 3px;
 }}
-|CAPTION=Schritt 1: Die kleinsten ausgehenden Kanten von <math>C</math> und <math>E</math> sind zugleich die kleinsten ausgehenden Kanten von <math>A</math> und <math>B</math>.
+|CAPTION=Schritt 1: Die kleinsten ausgehenden Kanten von <math>C</math> und <math>E</math><br>sind zugleich die kleinsten ausgehenden Kanten von <math>A</math> und <math>B</math>.
 |ALIGN=left
 |CLASS=noclear}}
@@ Zeile 142: / Zeile 142: @@
 linkStyle 0 stroke:red, stroke-width: 3px;
 }}
-|CAPTION=Schritt 3: Die kleinste ausgehende Kante von <math>\{A,C,D\}</math> ist zugleich die kleinste ausgehende Kante von <math>\{B,E\}</math>.
+|CAPTION=Schritt 3: Die kleinste ausgehende Kante von <math>\{A,C,D\}</math><br>ist zugleich die kleinste ausgehende Kante von <math>\{B,E\}</math>.
 |ALIGN=left
 |CLASS=noclear}}