Borůvka-Algorithmus

Aus KGS-Wiki

Version vom 29. März 2023, 07:34 Uhr von Sn (Diskussion | Beiträge) (Artikel ersrtellt)

(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

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.

Abgerufen von „https://wiki.kah.gs/index.php?title=Borůvka-Algorithmus&oldid=3048“