Kruskal-Algorithmus: Unterschied zwischen den Versionen
Aus KGS-Wiki
Sn (Diskussion | Beiträge) K (Navileiste) |
Sn (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
||
| Zeile 1: | Zeile 1: | ||
{{Thumbnailbox| | |||
INHALT={{#mermaid:graph LR | |||
{{#mermaid:graph LR | |||
a((A)) | a((A)) | ||
b((B)) | b((B)) | ||
| Zeile 15: | Zeile 14: | ||
d -- 7 --- e | d -- 7 --- e | ||
}} | }} | ||
|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 gewichteten [[Graph|Graphen]] einen minimalen [[Baum (Datenstruktur)|Spannbaum]] erzeugt. | ||
Version vom 29. März 2023, 06:37 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]
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
Algorithmen auf Graphen
Suche: Breitensuche | Tiefensuche
Kürzeste Wege: Dijkstra-Algorithmus | Bellman-Ford-Algorithmus
Minimale Spannbäume: Kruskal-Algorithmus | Prim-Algorithmus | Borůvka-Algorithmus
