Nächste Seite: Speichermöglichkeiten von Datenmengen mit Aufwärts: Hauptseite Algorithmen Vorherige Seite: Union-Find-Wälder Inhalt
Unterabschnitte
Kruskal zur Erstellung des MST
Abbruchkriterium
Sobald der Graph genau
Kanten hat, können wir abbrechen, da sonst ein Zyklus sofort erzeugt wird.
Laufzeit
Die Laufzeit des alleinigen Kruskalalgorithmus ist wegen der Sortierung
. Dazu muß allerdings noch der Zyklentest kommen, der mittels BFS oder DFS in 
-mal läuft.