Borůvka-Algorithmus: Unterschied zwischen den Versionen

Aus KGS-Wiki
← Zum vorherigen VersionsunterschiedZum nächsten Versionsunterschied →
VisuellWikitext
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 C und E
sind zugleich die kleinsten ausgehenden Kanten von A und B.
Schritt 2: Fasse {A,C,D} und {B,E} zu Zusammenhangskomponenten zusammen.
Schritt 3: Die kleinste ausgehende Kante von {A,C,D}
ist zugleich die kleinste ausgehende Kante von {B,E}.
Schritt 3: {A,B,C,D,E} bilden nun eine Zusammenhangskomponente.

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

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