Borůvka-Algorithmus: Unterschied zwischen den Versionen

Aus KGS-Wiki
(Artikel ersrtellt)
 
K (Kategorien)
Zeile 26: Zeile 26:
## Füge zu jeder [[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.
{{Navigationsleiste Graphalgorithmen}}
{{Navigationsleiste Graphalgorithmen}}
[[Kategorie:Graphen]]
[[Kategorie:Algorithmen]]

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

  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.
Abgerufen von „https://wiki.kah.gs/index.php?title=Borůvka-Algorithmus&oldid=3051“