Kruskal-Algorithmus: Unterschied zwischen den Versionen
Sn (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
Sn (Diskussion | Beiträge) (Ausführung begonnen) |
||
| Zeile 19: | Zeile 19: | ||
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> | ||
== Beispiel == | |||
So erzeugt der Kruskal-Algorithmus aus dem Beispielgraphen einen MST: | |||
=== Schritt 1 === | |||
{{#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:red; | |||
}} | |||
{{Lückenhaft}} | |||
== Weblinks == | == Weblinks == | ||
Version vom 30. März 2023, 12:35 Uhr
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
In diesem Artikel oder Abschnitt fehlen noch wichtige Informationen.
Hilf dem KGS-Wiki, indem du sie recherchierst und einfügst.
Weblinks
Quellen
- ↑ Joseph Kruskal: On the shortest spanning subtree and the traveling salesman problem. In: Proceedings of the American Mathematical Society, 7, 1956, S. 48–50
Suche: Breitensuche | Tiefensuche
Kürzeste Wege: Dijkstra-Algorithmus | Bellman-Ford-Algorithmus
Minimale Spannbäume: Kruskal-Algorithmus | Prim-Algorithmus | Borůvka-Algorithmus
