Borůvka-Algorithmus: Unterschied zwischen den Versionen

Aus KGS-Wiki
KKeine Bearbeitungszusammenfassung
K (Beispielgraphen durch Vorlageneinbindung ersetzt (sooooo guuuuuut...))
 
(6 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 1: Zeile 1:
{{Thumbnailbox|
{{Thumbnailbox|
INHALT={{#mermaid:graph LR
INHALT={{Beispielgraph}}
a((A))
b((B))
c((C))
d((D))
e((E))
a -- 3 --- b
a -- 1 --- c
b -- 7 --- c
b -- 5 --- d
b -- 1 --- e
c -- 2 --- d
d -- 7 --- e
}}
|CAPTION=Ein Beispielgraph}}
|CAPTION=Ein Beispielgraph}}


Zeile 23: Zeile 10:
# Erzeuge einen neuen Graphen <code>T</code>, der später der gesuchte Spannbaum wird.
# Erzeuge einen neuen Graphen <code>T</code>, der später der gesuchte Spannbaum wird.
# Füge alle Knoten, aber keine Kanten des Graphen <code>G</code> zu <code>T</code> hinzu.
# Füge alle Knoten, aber keine Kanten des Graphen <code>G</code> zu <code>T</code> hinzu.
# Wiederhole die folgenden Schritte, bis <code>T</code> [[Zusammenhang (Graph)|zusammenhängend]] ist:
# Wiederhole die folgenden Schritte, bis <code>T</code> [[Graph#(Un-)zusammenhängende_Graphen|zusammenhängend]] ist:
## Füge zu jeder [[Zusammenhang (Graphen)#Zusammenhangskomponente|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.


== Beispiel ==
== Beispiel ==
Zeile 33: Zeile 20:
|INHALT=
|INHALT=
{{Thumbnailbox|
{{Thumbnailbox|
INHALT={{#mermaid:graph LR
INHALT={{Beispielgraph|A=red|B=green|C=blue|D=purple|E=orange|link=lightgray}}
a((A))
b((B))
c((C))
d((D))
e((E))
a -- 3 --- b
a -- 1 --- c
b -- 7 --- c
b -- 5 --- d
b -- 1 --- e
c -- 2 --- d
d -- 7 --- e
classDef default stroke-width: 3px;
style a stroke:red;
style b stroke:green;
style c stroke:blue;
style d stroke:purple;
style e stroke:orange;
linkStyle default stroke:lightgray, fill:none;
}}
|CAPTION=Vorbereitung: Jeder Knoten bildet eine eigene Zusammenhangskomponente.
|CAPTION=Vorbereitung: Jeder Knoten bildet eine eigene Zusammenhangskomponente.
|ALIGN=left
|ALIGN=left
Zeile 59: Zeile 26:


{{Thumbnailbox|
{{Thumbnailbox|
INHALT={{#mermaid:graph LR
INHALT={{Beispielgraph|A=red|B=green|C=blue|D=purple|E=orange|link=lightgray|AC=red|BE=green|CD=purple}}
a((A))
|CAPTION=Schritt 1: Die kleinsten ausgehenden Kanten von <math>C</math> und <math>E</math><br>sind zugleich die kleinsten ausgehenden Kanten von <math>A</math> und <math>B</math>.
b((B))
c((C))
d((D))
e((E))
a -- 3 --- b
a -- 1 --- c
b -- 7 --- c
b -- 5 --- d
b -- 1 --- e
c -- 2 --- d
d -- 7 --- e
classDef default stroke-width: 3px;
style a stroke:red;
style b stroke:green;
style c stroke:blue;
style d stroke:purple;
style e stroke:orange;
linkStyle default stroke:lightgray, fill:none;
linkStyle 1 stroke:red, stroke-width: 3px;
linkStyle 4 stroke:green, stroke-width: 3px;
linkStyle 5 stroke:purple, stroke-width: 3px;
}}
|CAPTION=Schritt 1: Die kleinsten ausgehenden Kanten von <math>C</math> und <math>E</math> sind zugleich die kleinsten ausgehenden Kanten von <math>A</math> und <math>B</math>.
|ALIGN=left
|ALIGN=left
|CLASS=noclear}}
|CLASS=noclear}}


{{Thumbnailbox|
{{Thumbnailbox|
INHALT={{#mermaid:graph LR
INHALT={{Beispielgraph|A=red|B=green|C=red|D=red|E=green|link=lightgray|AC=red|BE=green|CD=red|ADDITA=subgraph acd["{A, C, D}"]; a; c; d; end; subgraph be["{B, E}"]; b; e; end; style acd stroke:red, stroke-width: 3px; style be stroke:green, stroke-width: 3px;}}
a((A))
b((B))
c((C))
d((D))
e((E))
a -- 3 --- b
a -- 1 --- c
b -- 7 --- c
b -- 5 --- d
b -- 1 --- e
c -- 2 --- d
d -- 7 --- e
classDef default stroke-width: 3px;
style a stroke:red;
style b stroke:green;
style c stroke:red;
style d stroke:red;
style e stroke:green;
linkStyle default stroke:lightgray, fill:none;
linkStyle 1 stroke:red, stroke-width: 3px;
linkStyle 4 stroke:green, stroke-width: 3px;
linkStyle 5 stroke:red, stroke-width: 3px;
}}
|CAPTION=Schritt 2: Fasse <math>\{A,C,D\}</math> und <math>\{B,E\}</math> zu Zusammenhangskomponenten zusammen.
|CAPTION=Schritt 2: Fasse <math>\{A,C,D\}</math> und <math>\{B,E\}</math> zu Zusammenhangskomponenten zusammen.
|ALIGN=left
|ALIGN=left
Zeile 117: Zeile 38:


{{Thumbnailbox|
{{Thumbnailbox|
INHALT={{#mermaid:graph LR
INHALT={{Beispielgraph|A=red|B=green|C=red|D=red|E=green|link=lightgray|AC=red|BE=green|CD=red|AB=red|ADDITA=subgraph acd["{A, C, D}"]; a; c; d; end; subgraph be["{B, E}"]; b; e; end; style acd stroke:red, stroke-width: 3px; style be stroke:green, stroke-width: 3px;}}
a((A))
|CAPTION=Schritt 3: Die kleinste ausgehende Kante von <math>\{A,C,D\}</math><br>ist zugleich die kleinste ausgehende Kante von <math>\{B,E\}</math>.
b((B))
c((C))
d((D))
e((E))
a -- 3 --- b
a -- 1 --- c
b -- 7 --- c
b -- 5 --- d
b -- 1 --- e
c -- 2 --- d
d -- 7 --- e
classDef default stroke-width: 3px;
style a stroke:red;
style b stroke:green;
style c stroke:red;
style d stroke:red;
style e stroke:green;
linkStyle default stroke:lightgray, fill:none;
linkStyle 1 stroke:red, stroke-width: 3px;
linkStyle 4 stroke:green, stroke-width: 3px;
linkStyle 5 stroke:red, stroke-width: 3px;
linkStyle 0 stroke:red, stroke-width: 3px;
}}
|CAPTION=Schritt 3: Die kleinste ausgehende Kante von <math>\{A,C,D\}</math> ist zugleich die kleinste ausgehende Kante von <math>\{B,E\}</math>.
|ALIGN=left
|ALIGN=left
|CLASS=noclear}}
|CLASS=noclear}}


{{Thumbnailbox|
{{Thumbnailbox|
INHALT={{#mermaid:graph LR
INHALT={{Beispielgraph|A=red|B=red|C=red|D=red|E=red|link=lightgray|AC=red|BE=red|CD=red|AB=red|ADDITA=subgraph abcde["{A, B, C, D, E}"]; a; b; c; d; e; end; style abcde stroke:red, stroke-width: 3px;}}
a((A))
b((B))
c((C))
d((D))
e((E))
a -- 3 --- b
a -- 1 --- c
b -- 7 --- c
b -- 5 --- d
b -- 1 --- e
c -- 2 --- d
d -- 7 --- e
classDef default stroke:red, stroke-width: 3px;linkStyle default stroke:lightgray, fill:none;
linkStyle 1 stroke:red, stroke-width: 3px;
linkStyle 4 stroke:red, stroke-width: 3px;
linkStyle 5 stroke:red, stroke-width: 3px;
linkStyle 0 stroke:red, stroke-width: 3px;
}}
|CAPTION=Schritt 3: <math>\{A,B,C,D,E\}</math> bilden nun eine Zusammenhangskomponente.
|CAPTION=Schritt 3: <math>\{A,B,C,D,E\}</math> bilden nun eine Zusammenhangskomponente.
|ALIGN=left
|ALIGN=left

Aktuelle Version vom 4. Dezember 2023, 15:14 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=3387“