Borůvka-Algorithmus: Unterschied zwischen den Versionen

Version vom 29. März 2023, 08:43 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.

Visualisierung von jedem Schritt des Boruvka's Algorithmus

@@ Zeile 25: / Zeile 25: @@
 # Wiederhole die folgenden Schritte, bis <code>T</code> zusammenhängend ist:
 ## Füge zu jeder [[Zusammenhangskomponente]] von <code>T</code> deren kleinste ausgehende Kante in <code>G</code> hinzu.
+[[Datei:Boruvka's algorithm (Sollin's algorithm) Anim.gif|mini|Visualisierung von jedem Schritt des Boruvka's Algorithmus]]
 {{Navigationsleiste Graphalgorithmen}}
 [[Kategorie:Graphen]]
 [[Kategorie:Algorithmen]]