Kruskal-Algorithmus: Unterschied zwischen den Versionen
Sn (Diskussion | Beiträge) K (Layout (final!)) |
Sn (Diskussion | Beiträge) |
||
| Zeile 39: | Zeile 39: | ||
c -- 2 --- d | c -- 2 --- d | ||
d -- 7 --- e | d -- 7 --- e | ||
linkStyle default stroke:lightgray, fill:none; | |||
linkStyle 1 stroke:#00b169, color:green; | linkStyle 1 stroke:#00b169, color:green; | ||
}} | }} | ||
| Zeile 58: | Zeile 59: | ||
c -- 2 --- d | c -- 2 --- d | ||
d -- 7 --- e | d -- 7 --- e | ||
linkStyle default stroke:lightgray, fill:none; | |||
linkStyle 1 stroke:#00b169, color:green; | linkStyle 1 stroke:#00b169, color:green; | ||
linkStyle 4 stroke:#00b169, color:green; | linkStyle 4 stroke:#00b169, color:green; | ||
}} | }} | ||
|CAPTION=Schritt 2 | |CAPTION=Schritt 2 | ||
|ALIGN=left | |ALIGN=left}} | ||
{{Thumbnailbox| | {{Thumbnailbox| | ||
| Zeile 79: | Zeile 80: | ||
c -- 2 --- d | c -- 2 --- d | ||
d -- 7 --- e | d -- 7 --- e | ||
linkStyle default stroke:lightgray, fill:none; | |||
linkStyle 1 stroke:#00b169, color:green; | linkStyle 1 stroke:#00b169, color:green; | ||
linkStyle 4 stroke:#00b169, color:green; | linkStyle 4 stroke:#00b169, color:green; | ||
| Zeile 100: | Zeile 102: | ||
c -- 2 --- d | c -- 2 --- d | ||
d -- 7 --- e | d -- 7 --- e | ||
linkStyle default stroke:lightgray, fill:none; | |||
linkStyle 1 stroke:#00b169, color:green; | linkStyle 1 stroke:#00b169, color:green; | ||
linkStyle 4 stroke:#00b169, color:green; | linkStyle 4 stroke:#00b169, color:green; | ||
| Zeile 106: | Zeile 109: | ||
}} | }} | ||
|CAPTION=Schritt 4 | |CAPTION=Schritt 4 | ||
|ALIGN=left | |ALIGN=left}} | ||
}} | }} | ||
Nach dem vierten Schritt gibt es keine Kante mehr, die keinen Kreis erzeugt, der Algorithmus | Je nach Implementierung könnte im ersten Schritt auch die Kante B—E ausgewählt werden. | ||
Nach dem vierten Schritt gibt es keine Kante mehr im Graphen, die keinen Kreis erzeugt, darum terminiert der Algorithmus. | |||
== Weblinks == | == Weblinks == | ||
Version vom 30. März 2023, 15:27 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:
Je nach Implementierung könnte im ersten Schritt auch die Kante B—E ausgewählt werden.
Nach dem vierten Schritt gibt es keine Kante mehr im Graphen, die keinen Kreis erzeugt, darum terminiert der Algorithmus.
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
