Borůvka-Algorithmus: Unterschied zwischen den Versionen

Aus KGS-Wiki
(Beispiel: Zusammenhangskomponenten besser visualisiert)
K (Graph-Layout)
Zeile 7: Zeile 7:
e((E))
e((E))
a -- 3 --- b
a -- 3 --- b
b -- 7 --- c
a -- 1 --- c
a -- 1 --- c
b -- 7 --- c
b -- 5 --- d
b -- 5 --- d
b -- 1 --- e
b -- 1 --- e
Zeile 40: Zeile 40:
e((E))
e((E))
a -- 3 --- b
a -- 3 --- b
b -- 7 --- c
a -- 1 --- c
a -- 1 --- c
b -- 7 --- c
b -- 5 --- d
b -- 5 --- d
b -- 1 --- e
b -- 1 --- e
Zeile 66: Zeile 66:
e((E))
e((E))
a -- 3 --- b
a -- 3 --- b
b -- 7 --- c
a -- 1 --- c
a -- 1 --- c
b -- 7 --- c
b -- 5 --- d
b -- 5 --- d
b -- 1 --- e
b -- 1 --- e
Zeile 79: Zeile 79:
style e stroke:orange;
style e stroke:orange;
linkStyle default stroke:lightgray, fill:none;
linkStyle default stroke:lightgray, fill:none;
linkStyle 1 stroke:red, stroke-width: 3px;
linkStyle 2 stroke:red, stroke-width: 3px;
linkStyle 4 stroke:green, stroke-width: 3px;
linkStyle 4 stroke:green, stroke-width: 3px;
linkStyle 5 stroke:purple, stroke-width: 3px;
linkStyle 5 stroke:purple, stroke-width: 3px;
Zeile 99: Zeile 99:
end
end
a -- 3 --- b
a -- 3 --- b
b -- 7 --- c
a -- 1 --- c
a -- 1 --- c
b -- 7 --- c
b -- 5 --- d
b -- 5 --- d
b -- 1 --- e
b -- 1 --- e
Zeile 114: Zeile 114:
style be stroke:green, stroke-width: 3px;
style be stroke:green, stroke-width: 3px;
linkStyle default stroke:lightgray, fill:none;
linkStyle default stroke:lightgray, fill:none;
linkStyle 1 stroke:red, stroke-width: 3px;
linkStyle 2 stroke:red, stroke-width: 3px;
linkStyle 4 stroke:green, stroke-width: 3px;
linkStyle 4 stroke:green, stroke-width: 3px;
linkStyle 5 stroke:red, stroke-width: 3px;
linkStyle 5 stroke:red, stroke-width: 3px;
Zeile 134: Zeile 134:
end
end
a -- 3 --- b
a -- 3 --- b
b -- 7 --- c
a -- 1 --- c
a -- 1 --- c
b -- 7 --- c
b -- 5 --- d
b -- 5 --- d
b -- 1 --- e
b -- 1 --- e
Zeile 149: Zeile 149:
style be stroke:green, stroke-width: 3px;
style be stroke:green, stroke-width: 3px;
linkStyle default stroke:lightgray, fill:none;
linkStyle default stroke:lightgray, fill:none;
linkStyle 1 stroke:red, stroke-width: 3px;
linkStyle 2 stroke:red, stroke-width: 3px;
linkStyle 4 stroke:green, stroke-width: 3px;
linkStyle 4 stroke:green, stroke-width: 3px;
linkStyle 5 stroke:red, stroke-width: 3px;
linkStyle 5 stroke:red, stroke-width: 3px;
Zeile 167: Zeile 167:
e((E))
e((E))
a -- 3 --- b
a -- 3 --- b
b -- 7 --- c
a -- 1 --- c
a -- 1 --- c
b -- 7 --- c
b -- 5 --- d
b -- 5 --- d
b -- 1 --- e
b -- 1 --- e
Zeile 176: Zeile 176:
classDef default stroke:red, stroke-width: 3px;linkStyle default stroke:lightgray, fill:none;
classDef default stroke:red, stroke-width: 3px;linkStyle default stroke:lightgray, fill:none;
style abcde stroke:red, stroke-width: 3px;
style abcde stroke:red, stroke-width: 3px;
linkStyle 1 stroke:red, stroke-width: 3px;
linkStyle 2 stroke:red, stroke-width: 3px;
linkStyle 4 stroke:red, stroke-width: 3px;
linkStyle 4 stroke:red, stroke-width: 3px;
linkStyle 5 stroke:red, stroke-width: 3px;
linkStyle 5 stroke:red, stroke-width: 3px;

Version vom 31. März 2023, 11:27 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.

Beispiel

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

Vorbereitung: Jeder Knoten bildet eine eigene Zusammenhangskomponente.
Schritt 1: Die kleinsten ausgehenden Kanten von und
sind zugleich die kleinsten ausgehenden Kanten von und .
Schritt 2: Fasse und zu Zusammenhangskomponenten zusammen.
Schritt 3: Die kleinste ausgehende Kante von
ist zugleich die kleinste ausgehende Kante von .
Schritt 3: bilden nun eine Zusammenhangskomponente.

Da nun zusammenhängend ist, terminiert der Algorithmus.

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