Borůvka-Algorithmus

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:

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

Beispiel

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

Vorbereitung: Jeder Knoten bildet eine eigene Zusammenhangskomponente.

Schritt 1: Die kleinsten ausgehenden Kanten von $C$ und $E$ sind zugleich die kleinsten ausgehenden Kanten von $A$ und $B$.

Schritt 2: Fasse $\{A,C,D\}$ und $\{B,E\}$ zu Zusammenhangskomponenten zusammen.

Schritt 3: Die kleinste ausgehende Kante von $\{A,C,D\}$ ist zugleich die kleinste ausgehende Kante von $\{B,E\}$.

Schritt 3: $\{A,B,C,D,E\}$ bilden nun eine Zusammenhangskomponente.

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

Algorithmen auf Graphen

Suche: Breitensuche | Tiefensuche

Kürzeste Wege: Dijkstra-Algorithmus | Bellman-Ford-Algorithmus

Minimale Spannbäume: Kruskal-Algorithmus | Prim-Algorithmus | Borůvka-Algorithmus