Kruskal-Algorithmus: Unterschied zwischen den Versionen

Aus KGS-Wiki
K (Graph-Layout)
Markierung: Manuelle Zurücksetzung
 
(5 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
b -- 7 --- c
a -- 1 --- c
b -- 5 --- d
b -- 1 --- e
c -- 2 --- d
d -- 7 --- e
}}
|CAPTION=Ein Beispielgraph}}
|CAPTION=Ein Beispielgraph}}


Der [[Kruskal-Algorithmus]] ist ein [[Algorithmus]], der zu einem gegebenen gewichteten [[Graph|Graphen]] einen minimalen [[Baum (Datenstruktur)|Spannbaum]] erzeugt.
Der [[Kruskal-Algorithmus]] ist ein [[Algorithmus]], der zu einem gegebenen [[Graph#(Un-)Gewichtete Graphen|gewichteten Graphen]] einen minimalen [[Baum (Datenstruktur)|Spannbaum]] erzeugt.


Der Algorithmus wurde 1956 von Joseph Kruskal entworfen und wie folgt beschrieben:<blockquote>Führe den folgenden Schritt so oft wie möglich aus: Wähle unter den noch nicht ausgewählten Kanten von <math>G</math> (dem Graphen) die kürzeste Kante, die mit den schon gewählten Kanten keinen Kreis bildet.<ref name="KRUSKAL">[[Joseph Kruskal]]: ''On the shortest spanning subtree and the traveling salesman problem.'' In: ''Proceedings of the American Mathematical Society'', 7, 1956, S. 48–50</ref></blockquote>
Der Algorithmus wurde 1956 von Joseph Kruskal entworfen und wie folgt beschrieben:<blockquote>Führe den folgenden Schritt so oft wie möglich aus: Wähle unter den noch nicht ausgewählten Kanten von <math>G</math> (dem Graphen) die kürzeste Kante, die mit den schon gewählten Kanten keinen Kreis bildet.<ref name="KRUSKAL">[[Joseph Kruskal]]: ''On the shortest spanning subtree and the traveling salesman problem.'' In: ''Proceedings of the American Mathematical Society'', 7, 1956, S. 48–50</ref></blockquote>
Zeile 26: Zeile 13:
{{Hinweisbaustein|style=padding:none; border:none;|INHALT=
{{Hinweisbaustein|style=padding:none; border:none;|INHALT=
{{Thumbnailbox|
{{Thumbnailbox|
INHALT={{#mermaid:graph LR
INHALT={{Beispielgraph|AC=#00b169}}
a((A))
b((B))
c((C))
d((D))
e((E))
a -- 3 --- b
b -- 7 --- c
a -- 1 --- c
b -- 5 --- d
b -- 1 --- e
c -- 2 --- d
d -- 7 --- e
linkStyle default stroke:lightgray, fill:none;
linkStyle 2 stroke:#00b169, color:green;
}}
|CAPTION=Schritt 1
|CAPTION=Schritt 1
|ALIGN=left
|ALIGN=left
Zeile 47: Zeile 19:


{{Thumbnailbox|
{{Thumbnailbox|
INHALT={{#mermaid:graph LR
INHALT={{Beispielgraph|AC=#00b169|BE=#00b169}}
a((A))
b((B))
c((C))
d((D))
e((E))
a -- 3 --- b
b -- 7 --- c
a -- 1 --- c
b -- 5 --- d
b -- 1 --- e
c -- 2 --- d
d -- 7 --- e
linkStyle default stroke:lightgray, fill:none;
linkStyle 2 stroke:#00b169, color:green;
linkStyle 4 stroke:#00b169, color:green;
}}
|CAPTION=Schritt 2
|CAPTION=Schritt 2
|ALIGN=left
|ALIGN=left
Zeile 69: Zeile 25:


{{Thumbnailbox|
{{Thumbnailbox|
INHALT={{#mermaid:graph LR
INHALT={{Beispielgraph|AC=#00b169|BE=#00b169|CD=#00b169}}
a((A))
b((B))
c((C))
d((D))
e((E))
a -- 3 --- b
b -- 7 --- c
a -- 1 --- c
b -- 5 --- d
b -- 1 --- e
c -- 2 --- d
d -- 7 --- e
linkStyle default stroke:lightgray, fill:none;
linkStyle 2 stroke:#00b169, color:green;
linkStyle 4 stroke:#00b169, color:green;
linkStyle 5 stroke:#00b169, color:green;
}}
|CAPTION=Schritt 3
|CAPTION=Schritt 3
|ALIGN=left
|ALIGN=left
Zeile 92: Zeile 31:


{{Thumbnailbox|
{{Thumbnailbox|
INHALT={{#mermaid:graph LR
INHALT={{Beispielgraph|AC=#00b169|BE=#00b169|CD=#00b169|AB=#00b169}}
a((A))
b((B))
c((C))
d((D))
e((E))
a -- 3 --- b
b -- 7 --- c
a -- 1 --- c
b -- 5 --- d
b -- 1 --- e
c -- 2 --- d
d -- 7 --- e
linkStyle default stroke:lightgray, fill:none;
linkStyle 2 stroke:#00b169, color:green;
linkStyle 4 stroke:#00b169, color:green;
linkStyle 5 stroke:#00b169, color:green;
linkStyle 0 stroke:#00b169, color:green;
}}
|CAPTION=Schritt 4
|CAPTION=Schritt 4
|ALIGN=left
|ALIGN=left
Zeile 116: Zeile 37:
}}
}}


Je nach Implementierung könnte im ersten Schritt auch die Kante B—E ausgewählt werden.
Je nach Implementierung könnte im ersten Schritt auch die Kante <math>\overline{BE}</math> ausgewählt werden.


Nach dem vierten Schritt gibt es keine Kante mehr im Graphen, die keinen Kreis erzeugt, darum terminiert der Algorithmus.
Nach dem vierten Schritt gibt es keine Kante mehr im Graphen, die keinen Kreis erzeugt, darum terminiert der Algorithmus.
Zeile 122: Zeile 43:
== Weblinks ==
== Weblinks ==


* [https://visualgo.net/en/mst Der Kruskal-Algorithmus visualisiert auf VisuAlgo.net 🇬🇧]
* {{VisuAlgo|en/mst|Der Kruskal-Algorithmus visualisiert}}


== Quellen ==
== Quellen ==

Aktuelle Version vom 1. April 2024, 01:38 Uhr

Ein Beispielgraph

Der Kruskal-Algorithmus ist ein Algorithmus, der zu einem gegebenen gewichteten Graphen einen minimalen Spannbaum erzeugt.

Der Algorithmus wurde 1956 von Joseph Kruskal entworfen und wie folgt beschrieben:

Führe den folgenden Schritt so oft wie möglich aus: Wähle unter den noch nicht ausgewählten Kanten von (dem Graphen) die kürzeste Kante, die mit den schon gewählten Kanten keinen Kreis bildet.[1]

Beispiel

So erzeugt der Kruskal-Algorithmus aus dem Beispielgraphen einen MST:

Schritt 1
Schritt 2
Schritt 3
Schritt 4

Je nach Implementierung könnte im ersten Schritt auch die Kante ausgewählt werden.

Nach dem vierten Schritt gibt es keine Kante mehr im Graphen, die keinen Kreis erzeugt, darum terminiert der Algorithmus.

Weblinks

Quellen

  1. ↑ Joseph Kruskal: On the shortest spanning subtree and the traveling salesman problem. In: Proceedings of the American Mathematical Society, 7, 1956, S. 48–50
Abgerufen von „https://wiki.kah.gs/index.php?title=Kruskal-Algorithmus&oldid=4114“