Kruskal-Algorithmus: Unterschied zwischen den Versionen

Aus KGS-Wiki
(Ausführung begonnen)
(Ablauf)
Zeile 24: Zeile 24:
So erzeugt der Kruskal-Algorithmus aus dem Beispielgraphen einen MST:
So erzeugt der Kruskal-Algorithmus aus dem Beispielgraphen einen MST:


=== Schritt 1 ===
{{Thumbnailbox|
{{#mermaid:graph LR
INHALT={{#mermaid:graph LR
a((A))
a((A))
b((B))
b((B))
Zeile 38: Zeile 38:
c -- 2 --- d
c -- 2 --- d
d -- 7 --- e
d -- 7 --- e
linkStyle 1 stroke:red;
linkStyle 1 stroke:#00b169, color:green;
}}
}}
|CAPTION=Schritt 1
|ALIGN=left}}


{{Lückenhaft}}
{{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
linkStyle 1 stroke:#00b169, color:green;
linkStyle 4 stroke:#00b169, color:green;
}}
|CAPTION=Schritt 2
|ALIGN=left}}
 
{{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
linkStyle 1 stroke:#00b169, color:green;
linkStyle 4 stroke:#00b169, color:green;
linkStyle 5 stroke:#00b169, color:green;
}}
|CAPTION=Schritt 3
|ALIGN=left}}
 
{{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
linkStyle 1 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
|ALIGN=left}}
 
Nach dem vierten Schritt gibt es keine Kante mehr, die keinen Kreis erzeugt, der Algorithmus terminiert.


== Weblinks ==
== Weblinks ==

Version vom 30. März 2023, 13:50 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

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

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=3060“