Borůvka-Algorithmus: Unterschied zwischen den Versionen

Aus KGS-Wiki
K (Kategorien)
(Gif)
Zeile 25: Zeile 25:
# Wiederhole die folgenden Schritte, bis <code>T</code> zusammenhängend ist:
# 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.
## 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}}
{{Navigationsleiste Graphalgorithmen}}
[[Kategorie:Graphen]]
[[Kategorie:Graphen]]
[[Kategorie:Algorithmen]]
[[Kategorie:Algorithmen]]

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:

  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.
Visualisierung von jedem Schritt des Boruvka's Algorithmus
Abgerufen von „https://wiki.kah.gs/index.php?title=Borůvka-Algorithmus&oldid=3055“