Borůvka-Algorithmus

Aus KGS-Wiki
(Weitergeleitet von Boruvka-Algorithmus)
3
7
1
5
1
2
7
A
B
C
D
E
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.

Beispiel

So erzeugt der Borůvka-Algorithmus aus dem Beispielgraphen einen MST:

3
7
1
5
1
2
7
A
B
C
D
E
Vorbereitung: Jeder Knoten bildet eine eigene Zusammenhangskomponente.
3
7
1
5
1
2
7
A
B
C
D
E
Schritt 1: Die kleinsten ausgehenden Kanten von C und E
sind zugleich die kleinsten ausgehenden Kanten von A und B.
{B, E}
{A, C, D}
3
7
1
5
1
2
7
B
E
A
C
D
Schritt 2: Fasse {A,C,D} und {B,E} zu Zusammenhangskomponenten zusammen.
{B, E}
{A, C, D}
3
7
1
5
1
2
7
B
E
A
C
D
Schritt 3: Die kleinste ausgehende Kante von {A,C,D}
ist zugleich die kleinste ausgehende Kante von {B,E}.
{A, B, C, D, E}
3
7
1
5
1
2
7
A
B
C
D
E
Schritt 3: {A,B,C,D,E} bilden nun eine Zusammenhangskomponente.

Da T nun zusammenhängend ist, terminiert der Algorithmus.

Diese Seite wurde von einer Lehrkraft überprüft.
Abgerufen von „https://wiki.kah.gs/index.php?title=Borůvka-Algorithmus&oldid=3387“