Borůvka-Algorithmus: Unterschied zwischen den Versionen

Version vom 2. Oktober 2023, 13:47 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 23: / Zeile 23: @@
 # Erzeuge einen neuen Graphen <code>T</code>, der später der gesuchte Spannbaum wird.
 # Füge alle Knoten, aber keine Kanten des Graphen <code>G</code> zu <code>T</code> hinzu.
-# Wiederhole die folgenden Schritte, bis <code>T</code> [[Zusammenhang (Graph)|zusammenhängend]] ist:
+# Wiederhole die folgenden Schritte, bis <code>T</code> [[Graph#(Un-)zusammenhängende_Graphen|zusammenhängend]] ist:
-## Füge zu jeder [[Graph#(Un-)zusammenhängende_Graphen|Zusammenhangskomponente]] von <code>T</code> deren kleinste ausgehende Kante in <code>G</code> hinzu.
+## Füge zu jeder Zusammenhangskomponente von <code>T</code> deren kleinste ausgehende Kante in <code>G</code> hinzu.
 == Beispiel ==