Kruskal-Algorithmus: Unterschied zwischen den Versionen
Sn (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung Markierung: Manuelle Zurücksetzung |
Sn (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
||
| Zeile 61: | Zeile 61: | ||
}} | }} | ||
|CAPTION=Schritt 2 | |CAPTION=Schritt 2 | ||
|ALIGN=left}} | |ALIGN=left | ||
|CLASS=noclear}} | |||
{{Thumbnailbox| | {{Thumbnailbox| | ||
| Zeile 104: | Zeile 105: | ||
}} | }} | ||
|CAPTION=Schritt 4 | |CAPTION=Schritt 4 | ||
|ALIGN=left}} | |ALIGN=left | ||
|CLASS=noclear}} | |||
Nach dem vierten Schritt gibt es keine Kante mehr, die keinen Kreis erzeugt, der Algorithmus terminiert. | Nach dem vierten Schritt gibt es keine Kante mehr, die keinen Kreis erzeugt, der Algorithmus terminiert. | ||
Version vom 30. März 2023, 14:09 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:
Nach dem vierten Schritt gibt es keine Kante mehr, die keinen Kreis erzeugt, der Algorithmus terminiert.
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
