Borůvka-Algorithmus: Unterschied zwischen den Versionen

Aus KGS-Wiki
(Gif)
(Beispiel)
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]]
 
== Beispiel ==
 
So erzeugt der Borůvka-Algorithmus aus dem Beispielgraphen einen MST:
 
{{Hinweisbaustein|style=border: none; padding: none
|INHALT=
{{Thumbnailbox|
INHALT={{#mermaid:graph LR
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.
|ALIGN=left
|CLASS=noclear}}
}}
 
{{Thumbnailbox|
INHALT={{#mermaid:graph LR
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;
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
|CLASS=noclear}}
}}
 
{{Thumbnailbox|
INHALT={{#mermaid:graph LR
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.
|ALIGN=left
|CLASS=noclear}}
}}
 
{{Thumbnailbox|
INHALT={{#mermaid:graph LR
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;
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
|CLASS=noclear}}
}}
 
{{Thumbnailbox|
INHALT={{#mermaid:graph LR
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.
|ALIGN=left
|CLASS=noclear}}
}}
 
Da <math>T</math> nun zusammenhängend ist, terminiert der Algorithmus.
 
{{Navigationsleiste Graphalgorithmen}}
{{Navigationsleiste Graphalgorithmen}}
[[Kategorie:Graphen]]
[[Kategorie:Graphen]]
[[Kategorie:Algorithmen]]
[[Kategorie:Algorithmen]]

Version vom 30. März 2023, 16:10 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=3076“