Metraipolis › archive › dc_28abc3d706ab

Algorithmus von Kruskal — Wikipedia (de)

Source
Wikipedia (de)
Original
https://de.wikipedia.org/wiki/Algorithmus_von_Kruskal
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-17T03:15:18.611Z
SHA-256 of the archived text
184160c7b88e353d5298777c0b49d6e875661602121b47cb0c5c6fe64ddce4eb
Stable URL of this page
https://metraipolis.com/documento/dc_28abc3d706ab

How to cite

Algorithmus von Kruskal — Wikipedia (de) — Wikipedia (de), https://de.wikipedia.org/wiki/Algorithmus_von_Kruskal (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_28abc3d706ab (Metraipolis archive dc_28abc3d706ab, sha256 184160c7b88e353d5298777c0b49d6e875661602121b47cb0c5c6fe64ddce4eb)
BibTeX
@misc{dc28abc3d706ab,
  title = {Algorithmus von Kruskal — Wikipedia (de)},
  howpublished = {Wikipedia (de)},
  url = {https://de.wikipedia.org/wiki/Algorithmus_von_Kruskal},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_28abc3d706ab; sha256 184160c7b88e353d5298777c0b49d6e875661602121b47cb0c5c6fe64ddce4eb},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (de), https://de.wikipedia.org/wiki/Algorithmus_von_Kruskal. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Der Algorithmus von Kruskal ist ein Greedy-Algorithmus der Graphentheorie zur Berechnung minimaler Spannbäume von ungerichteten Graphen. Der Graph muss dazu zusammenhängend, kantengewichtet und endlich sein. Der Algorithmus stammt von Joseph Kruskal, der ihn 1956 in der Zeitschrift „Proceedings of the American Mathematical Society“ veröffentlichte. Er beschrieb ihn dort wie folgt: Führe den folgenden Schritt so oft wie möglich aus: Wähle unter den noch nicht ausgewählten Kanten von G {\displaystyle G} (dem Graphen) die kürzeste Kante, die mit den schon gewählten Kanten keinen Kreis bildet. Die kürzeste Kante bezeichnet dabei jeweils die Kante mit dem kleinsten Kantengewicht. Nach Abschluss des Algorithmus bilden die ausgewählten Kanten einen minimalen Spannbaum des Graphen. Wendet man den Algorithmus auf unzusammenhängende Graphen an, so berechnet er für jede Zusammenhangskomponente des Graphen einen minimalen Spannbaum. Diese Bäume bilden einen minimalen aufspannenden Wald.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in tedesco, in ordine alfabetico).
Fonte: Wikipedia in tedesco, voce «Algorithmus von Kruskal» — https://de.wikipedia.org/wiki/Algorithmus_von_Kruskal
Wikidata Q797860: «algoritmo utilizzato per calcolare gli alberi di supporto minimi di un grafo» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q797860
Autori: i contributori di Wikipedia (cronologia: https://de.wikipedia.org/wiki/Algorithmus_von_Kruskal?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 264896374, consultata il 2026-10-17T03:07:39.110Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: ad720925978506fbba2608e0af812b90d6d3b2da8ee77257019f0472a5e4c75b